Dynamic Programming

Question 1

Principle of Kadane’s Algorithm

Answer 1

localMax[I] = Math.Max(A[I], A[I] + localMax[I-1]);

=> at every index I, the problem is essentially finding the max of just 2 #s, A[I] && A[I] + localMax[I-1]
=> so recursively finding local maxItems, while local maximum[0] = A[0];
=> therefore, we only need to iterate through the array once, making the time complexity of this algorithm to be O(n)