Sponsored
Sponsored
The Peak-Valley Approach aims to identify opportunities where a buy (at a valley) and a sell (at a peak) transaction yields profit. The idea is to take advantage of every upward trend between valleys and peaks and sum up the differences.
Time Complexity: O(n), where n is the number of prices.
Space Complexity: O(1), no additional space is used.
1def maxProfit(prices):
2 profit = 0
3 for i in range(1, len(prices)):
4 if prices[i] > prices[i - 1]:
5 profit += prices[i] - prices[i - 1]
6 return profit
7
8prices = [7,1,5,3,6,4]
9print("Max Profit:", maxProfit(prices))This Python solution iterates over each day's price compared to the previous day's, accumulating profits whenever the price increases. This strategy results in maximum profit by capitalizing on each rise.
The simple one-pass greedy approach makes a decision on each day based on whether the price will go up (buy or hold) or down (sell or do nothing). This maximizes profit by keeping solutions simple, efficient and using the greedy approach to sum up all local gains.
Time Complexity: O(n)
Space Complexity: O(1)
1#include <iostream>
int maxProfit(std::vector<int>& prices) {
int profit = 0;
for (size_t i = 1; i < prices.size(); ++i) {
profit += (prices[i] > prices[i - 1]) ? prices[i] - prices[i - 1] : 0;
}
return profit;
}
int main() {
std::vector<int> prices = {7,1,5,3,6,4};
std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
return 0;
}Using C++, the strategy is also greedy, where the solution boils down to adding up small profitable differences found between consecutive days of price increases.