Find a sub-array with the largest sum

Share

This problem is also known with the name: Maximum sum sub array problem/Largest sum contiguous sub array problem.

Problem: Given a one dimensional Array (containing both positive and negative numbers), write an efficient program to find a contiguous sub array in it which has a maximum sum.

Problem Explanation: You are given an array a = {1,3, -2, 8, -4, 0} So, all possible contiguous sub arrays present in a are:

{1}, {1,3}, {1,3,-2}, {1,3,-2,8}, {1,3,-2,8,-4}, {1,3,-2,8,-4,0}, {3}, {3,-2}, {3,-2,8}, {3,-2,8,-4}, {3,-2,8,-4,0}, {-2}, {-2,8}, {-2,8,-4}, {-2,8,-4,0}, {8}, {8,-4},
{8,-4,0}, {-4}, {-4,0}, {0}

now, find sum of each sub array found above and the answer would be the sub array which has the maximum sum among all…so, answer is: {1,3,-2,8,} with sum = 1+3+ (-2) + 8 = 10

Method 1: Below program is based on an algorithm/approach given by Kadane and popularly known as Kadane’s algorithm


public class MaxSumSubArray {
      // function to find maximum sum
      public static void maxSumSubArray(int[] a) {

           int maxSumFound = 0;
           int tempMaxSumFound = 0;
           int startIndex = 0;
           int endIndex = 0;

           for (int i = 0; i < a.length; i++) {
                      tempMaxSumFound += a[i];

                     if (tempMaxSumFound < 0) {
                             tempMaxSumFound = 0;
                             startIndex = i+1;
                    } else if (maxSumFound < tempMaxSumFound) {
                             maxSumFound = tempMaxSumFound;
                             endIndex = i;
                    }
           }

       System.out.println("Maximum Contingous sum found is: "+ maxSumFound);
       System.out.println("has startIndex: "+startIndex);
       System.out.println("has endIndex: "+endIndex);
      }

      // test function
      public static void main(String[] args) {

      //int[] a = { 1, 2, 3, -2, 0 };
        int[] a = { -1, -2, -3, -2};
       maxSumSubArray(a);
     }
}

Time Complexity: O(n) 

Solution Analysis: Method 1 is a good solution yet it misses one important case when all elements in the array are negative e.g {-1,-2} Method 2 below takes care of this case as well which has the same time complexity as Method 1 i.e O(n).

Method 2: The solution is almost same as Method 1 with a slight modification so as to handle the case when all elements in an array are negative.


public class MaxSumSubArray {
      // function to find maximum sum
      public static void maxSumSubArray(int[] a) {

           int maxSumFound = a[0];
           int tempMaxSumFound = a[0];
           int tempStartIndex = 0;
           int startIndex = 0;
           int endIndex = 0;

           for (int i = 1; i < a.length; i++) {

                      if (a[i] < tempMaxSumFound + a[i]) {
                               tempMaxSumFound = tempMaxSumFound + a[i];
                      } else {
                               tempMaxSumFound = a[i];
                               tempStartIndex = i;
                      }

                      if (maxSumFound < tempMaxSumFound) {
                               maxSumFound = tempMaxSumFound;
                               startIndex = tempStartIndex;
                               endIndex = i;
                      }
           }

      System.out.println("Maximum Contingous sum found is: " + maxSumFound);
      System.out.println("has startIndex: " + startIndex);
      System.out.println("has endIndex: " + endIndex);
     }

      // test function
      public static void main(String[] args) {

      //int[] a = { 1, 2, 3, -2, 0 };
        int[] a = { -1, -2, -3, -2};
       maxSumSubArray(a);
     }
}

Time Complexity: O(n) 

Solution Analysis: Method 2 is one of the best solutions to approach to this problem and works absolutely fine for an array containing all negative elements, all positive elements and a mix of positive and a negative elements.

Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)