leetcode/algorithms/maximum_profit2.cpp at master · hanfezh/leetcode · GitHub

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/*
 * =====================================================================================
 *
 *       Filename:  maximum_profit2.cpp
 *
 *    Description:  122. Best Time to Buy and Sell Stock II.
 *
 *        Version:  1.0
 *        Created:  09/06/18 02:39:36
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Zhu Xianfeng (), xianfeng.zhu@gmail.com
 *   Organization:
 *
 * =====================================================================================
 */

#include <vector>

#include "gtest/gtest.h"

// Peak Valley Approach
class Solution1 {
 public:
  int maxProfit(std::vector<int>& prices) {
    int max_profit = 0;
    int min_price = prices[0];
    int max_price = prices[0];

    for (int i = 1; i < prices.size(); i++) {
      if (prices[i] > max_price) {
        max_price = prices[i];
      } else {
        max_profit += max_price - min_price;
        min_price = prices[i];
        max_price = prices[i];
      }
    }
    max_profit += max_price - min_price;
    return max_profit;
  }
};

// Optimized solution
class Solution2 {
 public:
  int maxProfit(const std::vector<int>& prices) {
    int max_profit = 0;
    for (int i = 1; i < prices.size(); i++) {
      if (prices[i] > prices[i - 1]) {
        max_profit += prices[i] - prices[i - 1];
      }
    }
    return max_profit;
  }
};

TEST(Solution, maxProfit) {
  std::vector<std::pair<std::vector<int>, int>> cases = {
      {{7, 1, 5, 3, 6, 4}, 7},
      {{1, 2, 3, 4, 5}, 4},
      {{7, 6, 4, 3, 1}, 0},
  };
  for (auto& [prices, max_profit] : cases) {
    EXPECT_EQ(Solution1().maxProfit(prices), max_profit);
    EXPECT_EQ(Solution2().maxProfit(prices), max_profit);
  }
}