• 0

Maximum Sum subarray
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (3532)

Suppose you are given an integer array. How will you find the contiguous subarray with largest sum?


Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

The elements in the array are either all positive or positive and negative or all negative. We can use Kadane's algorithm as :


  • Iterate through the array from beginning to end and keep track of the current subarray sum.
  • If the current subarray sum is less than zero , the current subarray will be discarded in the computation of the the maximum sum subarray by initializing the current subarray sum to zero .
  • Return the maximum sum subarray when finished iterating.

The above algorithm will return zero when all the elements in the array is negative integers. The variable maximumSum represents the maximum sum.
Time complexity = \( O(n) \).

public static int[] findMaxSumSubarray(int[] array){

    /* Variables */
    int maximumSum = 0;
    int currentSum = 0;
    int currentStartIndex = 1;

    int maximumStartIndex = 0;
    int maximumEndIndex = 0;

    /* Iterate through the array from beginning to end */
    for(int currentEndIndex = 1; i  < = array.length; currentEndIndex++){

       /* Add the element at the current index to the currentSum and compare */
       currentSum += array[currentEndIndex];

       /* For positive integers */
       if(currentSum > maximumSum)
           maximumSum = currentSum;
           maximumStartIndex = currentStartIndex;
           maximumEndIndex = currentEndIndex;

       /* For negative integers */
       elseif(currentSum  <  0)
           currentSum = 0;
           currentStartIndex = currentEndIndex + 1;
           
    }
    /* Return the largest sum subarray */
    return Arrays.copyOfRange(array, maximumStartIndex, maximumEndIndex);
}
You need to Sign In to post your solution.