Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public int maxProfit(int[] prices) {
- if (prices.length < 2) {
- return 0;
- }
- int [] profit = new int[prices.length + 1];
- int [] sold_for = new int[prices.length];
- profit[0] = 0;
- profit[1] = 0;
- for (int i = 1; i < prices.length; i++) {
- if (prices[i] > prices[i-1]) {
- // can sell
- int additionalProfit = prices[i] - prices[i-1];
- sold_for[i-1] = prices[i];
- for (int j = i - 2; j >= 0; j--) {
- if (prices[j] >= prices[i]) {
- // got to a point where there was a point where the max > curr
- break;
- }
- additionalProfit += prices[i] - prices[j] - sold_for[j];
- sold_for[j] = prices[i];
- }
- profit[i + 1] = profit[i] + additionalProfit;
- }
- else {
- profit[i + 1] = profit[i];
- }
- }
- return profit[prices.length];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement