Find maximum sum subarray
  • subarray
  • array
  • dynamicprogramming
  • searching
  •   
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2360)

Suppose you are given a one dimensional array of arbitrary integers. How will you find the maximum sum sub-array?


Posted Answers

It can be solved using Kadane's algorithm.


    Iterate through the array from the beginning and compute the sum of the subarray ending at the current
    index.
    Compute the maximum of this current subarray sum and the value at current index. This maximum will be the current subarray sum.
    Compute the maximum of the current subarray sum and the maximum sum so far.
    Return the maximum in the last step once the whole array is iterated.


Time complexity = \( O(n) \).

public static int FindMaxSumSubArray(int[] array){

/* Maximum sum so far */
int maxSumSoFar = 0;

/* Maximum Ends here */
int maxEnd = 0;

/* Iterate through the array and compute the maximum sum so far */
for (int i = 0; i < array.length; i++){
maxEnd = Math.max(array[i], maxEnd + array[i]);
maxSumSofar = Math.max(maxSumSofar, maxEnd);
}

/* Return the maximum sum :: the result */
return maxSumSoFar;
}

You need to Sign In to post your solution.