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.
1#include <vector>
2#include <iostream>
3
4int maxProfit(std::vector<int>& prices) {
5 int profit = 0;
6 for (size_t i = 1; i < prices.size(); ++i) {
7 if (prices[i] > prices[i - 1]) {
8 profit += prices[i] - prices[i - 1];
9 }
10 }
11 return profit;
12}
13
14int main() {
15 std::vector<int> prices = {7,1,5,3,6,4};
16 std::cout << "Max Profit: " << maxProfit(prices) << std::endl;
17 return 0;
18}This C++ solution uses a similar logic to the C solution; it checks pairs of consecutive prices and adds the difference to profit if there is an upward trend. The vector 'prices' allows dynamic sizing suitable for market data use cases.
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
This solution applies a simple one-pass through the price list, capturing the upswing value each time prices rise day-over-day and summing these gains into total profit output.