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 <stdio.h>
2
3int maxProfit(int* prices, int pricesSize) {
4 int profit = 0;
5 for (int i = 1; i < pricesSize; i++) {
6 if (prices[i] > prices[i - 1]) {
7 profit += prices[i] - prices[i - 1];
8 }
9 }
10 return profit;
11}
12
13int main() {
14 int prices[] = {7,1,5,3,6,4};
15 int size = sizeof(prices) / sizeof(prices[0]);
16 printf("Max Profit: %d\n", maxProfit(prices, size));
17 return 0;
18}The code iterates over the price array. Whenever a profit opportunity is identified (when today's price is higher than yesterday's), the difference is added to the total profit. This maximizes profit by summing up all 'up-hill' gains directly.
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
The Python code follows a similar one-pass greedy tactic to accumulate profit by detecting each positive differential day-to-day, adding that to the resultant profit count.