Buy and sell stocks - Java, Greedy solution


  • 0
    D

    find profit for all the increasing subsequences in prices array:

    Eg:
    2 4 1 3 5 2 6
    seq1 : 2,4 => profit = 2
    seq2 : 1,3,5 => profit = 4
    seq 3 : 2,6 => profit = 4
    Total profit = 2 + 4 + 4 = 12

    public class Solution {
        public int maxProfit(int[] prices) {
            int sell = prices.length-1;
            int buy = 0;
            int curMax = 0, maxProfit = 0;
            
            for( buy = sell-1; buy >= 0; buy-- ) {
                int profit = prices[sell] - prices[buy];
                if( profit < curMax ) {
                    maxProfit += curMax;
                    curMax = 0;
                    sell = buy;
                }
                else {
                    curMax = profit;
                }
            }
            return maxProfit+curMax;
        }
    }
    

    Runtime: O(n)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.