package java_exercise; public class MaximumSubarray { /* * Find the contiguous subarray within an array (containing at least one number) which has the largest sum. * For example, given the array [−2,1,−3,4,−1,2,1,−5,4], * the contiguous subarray [4,−1,2,1] has the largest sum = 6. */ // for an array A[0, i], if there is a k so that the sum from A[k] to A[i] is the maximum, // we define it as max[i]. Then max[i+1] = max[i] + A[i+1] if (max[i] + A[i+1] > 0) or = 0 // if max[i+1] < 0. Because if max[i+1] < 0, A[i+1] must be a negative number. So we drop it. //O(n) Solution public int maxSubArray(int[] nums) { int sum = 0, max = Integer.MIN_VALUE; for (int i : nums) { sum += i; if (sum > max) max = sum; if (sum < 0) sum = 0; } return max; } //Divide and Conquer Solution }