Maximum subarray problem - Kadane algorithm (Solution in Java).

In Maximum subarray problem we are given one-dimensional array of numbers and in that array we have to find a contiguous subarray such that when we add all numbers of subarray the sum should be greater than sum of numbers of any other subarray within that array.  For example, in array {2,1,-4,5,-2,8,1,-2}
the subarray {5,-2,8,1} has sum=12 and that sum is maximum than all other subarrays.
This problem can be solved using varoius methods like brute force method O(N^2) or divide and conquer (nlogn).
But by using Kadane algorithm we can solve this problem in linear time O(N).

Note that this problem is interesting to solve only when array has both negative and positive numbers. Because if all elements of array are positive than subarray having maximum sum is complete array itself.
For example
5,0,1,2,7,2
maximum sum is 17 that is of complete array.
Also array should contain atleast one positive number to ensure that there is subarray with maximum sum.
Below program gives maximum value of sum of subarray numbers.

Java code:
class Main {
   
    static int kadane(int [] array){
        int max_ending_here = 0, max_so_far = 0;
        for (int i = 0; i < array.length; i++) {
            max_ending_here+=array[i];
            if(max_ending_here < 0){
                max_ending_here = 0;
            }else if(max_ending_here > max_so_far){
                max_so_far = max_ending_here;
            }
        }
        return max_so_far;
    }
   
    public static void main(String[] args) {
        int maxSum = kadane(new int[]{2,-3,4,-1,-2,1,5,-3});
        System.out.println("Maximum sum of subarray="+maxSum);
    }
}

Output:
Maximum sum of subarray=7

Explanation:
In kadane algorithm we take two int variables max_ending_here, max_so_far both initialized to 0 . In each iteration of for loop we add number at current index to max_ending_here and after that we check:
1. If max_ending_here becomes less than zero we reset max_ending_here back to zero.
2. Else if it greater than max_so_far we set max_so_far to max_ending_here.

So whenever max_ending_here becomes negative we reset it to zero because negative number will only reduce overall sum and previous maximum value of max_ending_here before it becomes negative is saved in max_so_far variable and max_so_far is changed only when max_ending_here becomes greater than max_so_far. Thus we compute maximum at each position.

Above program can be easily modified to find subarray having maximum sum.

Java code:

class Main {
   
    static int kadane(int [] array){
        int max_ending_here = 0, max_so_far = 0;
        int startIndex = 0, endIndex = 0, tmpStart = 0;       
      for (int i = 0; i < array.length; i++) {
            max_ending_here+=array[i];
            if(max_ending_here < 0){
                max_ending_here = 0;
                tmpStart = i + 1;
            }else if(max_ending_here > max_so_far){
                max_so_far = max_ending_here;
                startIndex = tmpStart;
                endIndex = i;
            }
        }
        if(startIndex <= endIndex){
            System.out.println("Subarray starts at startIndex="+startIndex+" and ends at endIndex="+endIndex);
            System.out.print("Subarray is:");
            for (int i = startIndex; i <= endIndex; i++) {
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }else{
            System.out.println("All numbers in array are negative or zero.");
        }
       
        return max_so_far;
    }
   
    public static void main(String[] args) {
        int maxSum = kadane(new int[]{2,-3,4,-1,-2,1,5,-3});
        if(maxSum > 0){
            System.out.println("Maximum sum of subarray="+maxSum);
        }
    }
}
Output:
Subarray starts at startIndex=2 and ends at endIndex=6
Subarray is:4 -1 -2 1 5
Maximum sum of subarray=7

Three new variables are introduced tmpStart, startIndex and endIndex to track subarray start and end position in array and both are initialised to 0. tmpStart is set to value of next index in array when max_ending_here becomes less than zero and startIndex is set to value of tmpStart in else condition.

Value of variables during course of program is listed in below table: