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.
public class Solution { public int maxSubArray(int[] A) { // Start typing your Java solution below // DO NOT write main() function int max = -1000; int sum = 0; for(int i = 0 ; i < A.length; i++){ sum = sum + A[i]; if(sum > max){ max = sum; } if(sum < 0) sum = 0; } return max; } }
public class Solution { public int maxSubArray(int[] A) { int max = A[0]; int[]sum = new int[A.length]; sum[0] = A[0]; for(int i = 1 ; i < A.length ; i++){ sum[i]+= Math.max(A[i],sum[i-1]+A[i]); max = Math.max(max,sum[i]); } return max; } }
python: class Solution: # @param A, a list of integers # @return an integer def maxSubArray(self, A): sum = 0 max = -99999 for i in A: sum += i if sum > max: max = sum if sum < 0 : sum = 0 return max