### Maximum Sum subarray subarray array searching    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: 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);}