Kadane's Algorithm - Since no one has mentioned about this so far :) (In case if interviewer twists the input)


  • 284

    The logic to solve this problem is same as "max subarray problem" using Kadane's Algorithm. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

    All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

    Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

        public int maxProfit(int[] prices) {
            int maxCur = 0, maxSoFar = 0;
            for(int i = 1; i < prices.length; i++) {
                maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
                maxSoFar = Math.max(maxCur, maxSoFar);
            }
            return maxSoFar;
        }
    

    *maxCur = current maximum value

    *maxSoFar = maximum value found so far


  • 13

    Please refer to this for more details on the algorithm : https://en.wikipedia.org/wiki/Maximum_subarray_problem


  • 0
    A

  • 0
    This post is deleted!

  • 30
    M

    Thanks for sharing! Almost like this answer, but you explanation is more clear! I have the same idea, it's little complex but straight forward. Hopes it can help someone to understand.

    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int diff[] = new int[prices.length-1];
        for(int i=1; i<prices.length; i++){
            diff[i-1] = prices[i] - prices[i-1];
        }
        return maxSubArray(diff);
    }
    public int maxSubArray(int[] nums) {
        if(nums.length<1) return 0;
        int preMax = 0, m = 0;
        for(int i=0; i<nums.length; i++){
            m = Math.max(m, preMax+nums[i]);
            preMax = Math.max(0, preMax+nums[i]);
        }
        return m;
    }
    

  • 0
    X

    Absolutely brilliant!!


  • 0
    This post is deleted!

  • -1
    W

    If the max subarray is negative,

    maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);

    maybe a bug


  • 3

    @willstudy
    If it is negative, then it is a loss, we shouldn't carry over the loss. So we start from fresh, by resetting it to 0.


  • 19
    R

    Hi, everybody! I want to share my thoughts of this algorithm, I will explain the recurrence formula below to help you guys understand this problem better.

    Why maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]); ?

    Well, we can assume opt(i) as the max Profit you will get if you sell the stock at day i;

    We now face two situations:

    1. We hold a stock at day i, which means opt(i) = opt(i - 1) - prices[i - 1] + prices[i] (max Profit you can get if you sell stock at day(i-1) - money you lose if you buy the stock at day (i-1) + money you gain if you sell the stock at day i.

    2. We do not hold a stock at day i, which means we cannot sell any stock at day i. In this case, money we can get at day i is 0;

    opt(i) is the best case of 1 and 2.

    So, opt(i) = Max{opt(i - 1) - prices[i - 1] + prices[i], 0}


  • 0
    S

    So if the question given is the difference array of prices like {0, 6, -3, 7}, does that mean maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]) will simply be changed to maxCur = Math.max(0, maxCur + prices[i])?


  • 1

    I'm little confused.. because Kadane's Algorithm is about subarray, while this question required that "only permitted to complete at most one transaction". I thought it only got 2 elements (in order, but not need to be contiguous) involved in the array.


  • 1
    Y

    Very clear solution by calling Kadane's Algorithm separately!


  • 2

    Thanks for pointing out the connection to max subarray problem.


  • 17

    @jaqenhgar
    I think u needn't update maxCur in this complex way, you can just keep a variable to help
    my solution here

            int min = Integer.MAX_VALUE, max = 0;
            for (int c: prices) {
                min = Math.min(c, min);
                max = Math.max(max, c - min);
            }
            return max;
    
    }

  • 9

    This is my solution, I think it's easier to understand.

    public int maxProfit(int[] prices) {
            int max = 0, min = Integer.MAX_VALUE;
            for (int i = 0; i < prices.length; i++) {
                if (prices[i] < min) min = prices[i];
                else if (prices[i] > min) max = Math.max(prices[i] - min, max);
            }
            return max;
        }
    

  • 0

    @zhugejunwei I got something pretty similar to what you have:

        public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            
            int minPrice = prices[0], profit = 0;
            for (int i = 1; i < prices.length; i++) { // Note: starts at index 1
                if (prices[i] > minPrice) {  // Note: seemingly superfluous if-check
                    profit = Math.max(profit, prices[i] - minPrice);
                }
                minPrice = Math.min(minPrice, prices[i]);
            }        
            return profit;
        }
    

    I notice that when I had the same above algorithm with the following modifications: start at index 0, and purge the if-check then my runtime was 4ms on the OJ. Adding these checks helps skip some work and brings it down to 2ms.


  • 0

    same here:

    public int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1) {
                return 0;
            }
            int buy = prices[0];
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > buy) {
                  profit = Math.max(profit, prices[i] - buy);
                } else {
                    buy = prices[i];
                }
            }
            return profit;
        }
    

    We buy at the first day as A, if later days price is higher, we can just calculate the difference as profit, once the price is below previous buy price as B, we need to adjust buy price from A to B. The sell price is C. C - B is definitely bigger than C - A and we also store each previous max profit and update it when necessary.


  • 0
    M

    Hey @jaqenhgar, what will be the answer if the prices array is {1,7,14} and the corresponding difference array is {0,6,7} ? I am not quite able to follow it.


  • 1
    J

    @wangshiqi The sum of all the difference between price[i] and price[i-1] where i = buy to sell equals to price[sell]-price[buy].


Log in to reply
 

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