Sunday, 19 July 2015

Solution for Maximum sum sub sequence or maximum sum sub array or maximum sum slice problem in java in O(n) time complexity.

Dear Friends,

Today I am here with a famous array based problem. The problem statement is as follows

Given an Array 'A' of integers of size 'n' , our objective is to find such a sub array from the original array such that the elements in the sub array are in the same order and sequence as in original array and  among all such sub arrays whose sum is maximum.

For example :
if we have a 0 indexed array, A = {-1,-2,0,4,1,2,3,4,0,9,-2,-3,0} , then here our sub array with the maximum sum is as below

{0,4,1,2,3,4,0,9} with the sum as 23, start index in the original array is 2 and end index is 9



Now lets look at the code for the same.

The idea followed is simple. Traverse the array and and keep on updating the global attributes for start, end and sum as new larger sum is found, and keep on adding elements to the local attributes till the local sum is positive, in an hope to find a positive number ahead which will make the sum greatest.  For the negative numbers our maximum sum will be the element with minimum absolute value, like {-8,-3,-5,-1,-3} here our maximum sum is obtained by just single element i.e. -1 , indexed at 3 as adding any other element from all negative valued array will only decrease the sum.



package com.algorithm.arrays.max_sub_sequence;

public class MaximumSumSubsequence {
 public static void main(String[] args) {
  MaximumSumSubsequence mss = new MaximumSumSubsequence();
  int[] a = { -10, -1, -2, 0, -1, 1, 7, 8, -1, 9};
  int sol = mss.solution(a);
  System.out.println(sol);
 }

 public int solution(int[] A) {
  int globalSum = Integer.MIN_VALUE;
  int localSum = 0;
  int globalStart = 0;
  int localStart = 0;
  int globalEnd = 0;
  int localEnd = 0;
  int n = A.length;
  boolean isAllNegative = true;
  int minIndexIfAllNegative = -1;
  int sumIfAllNegative = Integer.MIN_VALUE;
  for (int i = 0; i < n; i++) {
   if (localSum + A[i] >= 0) {
    localSum = localSum + A[i];
    localEnd = i;
    if (localStart == -1) {
     localStart = i;
    }
   } else {
    localStart = -1;
    localSum = 0;
   }

   if (localSum >= globalSum) {
    globalSum = localSum;
    globalStart = localStart;
    globalEnd = localEnd;
   }
   if (A[i] >= 0) {
    isAllNegative = false;
   } else {
    if (sumIfAllNegative < A[i]) {
     sumIfAllNegative = A[i];
     minIndexIfAllNegative = i; 
    }
   }
  }
  if (isAllNegative) {
   globalSum = sumIfAllNegative;
   globalStart = minIndexIfAllNegative;
   globalEnd = minIndexIfAllNegative;
  }
  System.out.println("start index: " + globalStart + " end index: " + globalEnd + " sum: " + globalSum);
  return globalSum;
 }
}