### Find maximum sum subarray subarray array dynamicprogramming searching    Posted: 6 years ago Edit answers (1) views (2720)

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

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