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

@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.

I think if you do

public int maxProfit(int[] prices) { int maxCur = 0, maxSoFar = 0; for(int i = 1; i < prices.length; i++) { maxCur = Math.max(prices[i] - prices[i-1], maxCur += prices[i] - prices[i-1]); maxSoFar = Math.max(maxCur, maxSoFar); } return maxSoFar; }The above code is still valid. Note that maxSoFar has a lower limit of 0. So even maxCur may be negative, it doesn't affect. In fact, this code is the original Kadane's algorithm.