Skip to content

2907. Maximum Profitable Triplets With Increasing Prices I 👍

  • Time: $O(n\log(\max(\texttt{prices})))$
  • Space: $O(\max(\texttt{prices}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class FenwickTree {
 public:
  FenwickTree(int n) : vals(n + 1) {}

  void maximize(int i, int val) {
    while (i < vals.size()) {
      vals[i] = max(vals[i], val);
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int res = 0;
    while (i > 0) {
      res = max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

 private:
  vector<int> vals;

  static int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  int maxProfit(vector<int>& prices, vector<int>& profits) {
    const int maxPrice = ranges::max(prices);
    int ans = -1;
    FenwickTree maxProfitTree1(maxPrice);
    FenwickTree maxProfitTree2(maxPrice);

    for (int i = 0; i < prices.size(); ++i) {
      const int price = prices[i];
      const int profit = profits[i];
      // max(proftis[i])
      const int maxProfit1 = maxProfitTree1.get(price - 1);
      // max(proftis[i]) + max(profits[j])
      const int maxProfit2 = maxProfitTree2.get(price - 1);
      maxProfitTree1.maximize(price, profit);
      if (maxProfit1 > 0)
        maxProfitTree2.maximize(price, profit + maxProfit1);
      if (maxProfit2 > 0)
        ans = max(ans, profit + maxProfit2);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class FenwickTree {
  public FenwickTree(int n) {
    vals = new int[n + 1];
  }

  public void maximize(int i, int val) {
    while (i < vals.length) {
      vals[i] = Math.max(vals[i], val);
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int res = 0;
    while (i > 0) {
      res = Math.max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

  private int[] vals;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public int maxProfit(int[] prices, int[] profits) {
    final int maxPrice = Arrays.stream(prices).max().getAsInt();
    int ans = -1;
    FenwickTree maxProfitTree1 = new FenwickTree(maxPrice);
    FenwickTree maxProfitTree2 = new FenwickTree(maxPrice);

    for (int i = 0; i < prices.length; ++i) {
      final int price = prices[i];
      final int profit = profits[i];
      // max(profits[i])
      final int maxProfit1 = maxProfitTree1.get(price - 1);
      // max(proftis[i]) + max(profits[j])
      final int maxProfit2 = maxProfitTree2.get(price - 1);
      maxProfitTree1.maximize(price, profit);
      if (maxProfit1 > 0)
        maxProfitTree2.maximize(price, profit + maxProfit1);
      if (maxProfit2 > 0)
        ans = Math.max(ans, profit + maxProfit2);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class FenwickTree:
  def __init__(self, n: int):
    self.vals = [0] * (n + 1)

  def maximize(self, i: int, val: int) -> None:
    while i < len(self.vals):
      self.vals[i] = max(self.vals[i], val)
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    res = 0
    while i > 0:
      res = max(res, self.vals[i])
      i -= FenwickTree.lowbit(i)
    return res

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def maxProfit(self, prices: list[int], profits: list[int]) -> int:
    ans = -1
    maxPrice = max(prices)
    maxProfitTree1 = FenwickTree(maxPrice)
    maxProfitTree2 = FenwickTree(maxPrice)

    for price, profit in zip(prices, profits):
      # max(proftis[i])
      maxProfit1 = maxProfitTree1.get(price - 1)
      # max(proftis[i]) + max(profits[j])
      maxProfit2 = maxProfitTree2.get(price - 1)
      maxProfitTree1.maximize(price, profit)
      if maxProfit1 > 0:
        maxProfitTree2.maximize(price, profit + maxProfit1)
      if maxProfit2 > 0:
        ans = max(ans, profit + maxProfit2)

    return ans