• Posted: 6 years ago
• Updated: 6 years ago
• 0 0
• Edit

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.

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;
 }