Write a Java program to find the largest sum of the contiguous subarray in a given Array

Write a Java program to find the largest sum of the contiguous subarray in a given Array. The given array might contain negative elements too and hence we need to find out a contiguous sub-array whose sum would be maximum.

The brute force approach would be to use a nested loop to find this subarray and the time-complexity for the same would be O(n^2) which is inefficient. This can be optimized to a time-complexity of O(n) with dynamic programming using Kadane’s algorithm.

This is one of the most asked interview programs for Java developers and we can solve many other problems using this particular algorithm such as maximum sum rectangle in a 2D matrix.

In this algorithm, we have two variables as bestSum and currentSum initialized to 0. For each iteration, we calculate the currentSum by adding the value present at the current index to the currentSum and update the bestSum with currentSum in case we find currentSum is greater than the bestSum. Else, the the current value of the best sum is the largest sum value so far.

Below is the sample java program for the same.

public class LargestSubArraySum {
    
    //print the sum of largest sub array
    public static void main(String[] args){
        int[] arr = {-1, 5, -50, -3, -90};
        int length = arr.length;
        int bestSum = 0;
        int currentSum = 0;
        for(int i =0; i < length; i++){
            currentSum = currentSum + arr[i];
            if(currentSum > bestSum){
                //Now, once the currentSum becomes more then bestSum the value of bestSum will be reset
                bestSum = currentSum;
            }else {
                //currentSum is less and hence reset the currentSum.
                currentSum  = 0;
            }
        }
        System.out.println(bestSum);
    }
}

5

Above program prints the largest contiguous subarray sum of a given array. With a little tweak, it is also possible to print the start and end index of the sub array.

public static void largestSumSubArray(int[] array){
        int i = 0;
        int j = 0;
        int bestSum = 0;
        int currentSum = 0;
        for (int k = 0; k < array.length; k++){
            currentSum = currentSum + array[k];
            if (currentSum > bestSum){
                bestSum = currentSum;
                j = k;
            }else {
                currentSum = 0;
                if (k <= j){
                    i = k + 1;
                }
            }
        }
        System.out.println("Max sub array start at " + i + " end at " + j);
    }