Leetcode-Data-Structures-and-Algorithms/DynamicProgramming/KadaneMaximumSumSubarray.java at master · 17tanya/Leetcode-Data-Structures-and-Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
https://www.techiedelight.com/maximum-subarray-problem-kadanes-algorithm/

We maintain 2 variables -
1. maxEndingHere - stores the maximum sum of the sub-array ending at the current index
    1.1. Include the current element in the sub-array sum
    1.2. Start a new sub-array from this element ie. sum = current element
2. maxSoFar - stores the maximum possible sum of all the sub-arrays
*/

public int kadane(int A[]){
    int n = A.length;

    if(n == 0) return 0;

    int maxEndingHere = A[0];
    int maxSoFar = A[0];

    for(int i=1 ; i < n ; i++){
        //include current element in the sub-array sum
        maxEndingHere+=A[i];

        //check if starting a new sub-array gives a greater sum than the current sum
        maxEndingHere = Math.max(maxEndingHere, A[i]);

        //update the overall max-sum
        maxSoFar = Math.max(maxEndingHere, maxSoFar);
    }

    return maxSoFar;
}

//Time Complexity - O(n)
//Traverses the array only once