# Accepted O(n) solution in java

• this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)

the paragraph below was copied from his paper (with a little modifications)

algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

``````public static int maxSubArray(int[] A) {
int maxSoFar=A[0], maxEndingHere=A[0];
for (int i=1;i<A.length;++i){
maxEndingHere= Math.max(maxEndingHere+A[i],A[i]);
maxSoFar=Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}``````

• Similar idea, reset if left sum is a negative value.

``````class Solution {
public:
int maxSubArray(int A[], int n) {
int maxSub = INT_MIN;
int leftPositive = 0;
for (int i = 0; i < n; i++) {
maxSub = max(maxSub, leftPositive + A[i]);
leftPositive = max(0, leftPositive + A[i]);
}
return maxSub;
}
};``````

• Hi, flyflybird. I happen to have a similar code :-)

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, smax = INT_MIN;
for (int num : nums) {
sum += num;
if (sum > smax) smax = sum;
if (sum < 0) sum = 0;
}
return smax;
}
};``````

• Even masters in computer science solved LeetCode problems in the past :-)

• Best and most clear approach that you can ever get. If still in doubt, check this video tutorial on Kaden's algorithm.

• Thanks for the explanation, good idea.

I think we should also consider `if (nums == null || nums.length == 0);`

• Elegant solution!

• ``````Who can tell me which is better,  Jon Bentley's Code is more efficient than the code below? WHY?

int maxSubArray(int* nums, int numsSize) {
register int cur = 0;
register int max = INT_MIN;
for(int i = 0; i < numsSize; i++){
cur += nums[i];                          // greedy to add num untill it smaller than 0
max  = cur > max ? cur : max;        // mark the max val during the adding
if(cur < 0)
cur = 0;
}
return max;
``````

}

• clear explanation . thanks for share

we can do the same with this relation

sum(0,i) = a[i] + (sum(0,i-1) < 0 ? 0 : sum(0,i-1))

this equation says that if previous sum is negative then no need to carry on with current sum=previous sum+current element since it will give lesser sum then the sum restarted with current element.

``````int maxSubArray(vector<int>& nums) {
int n=nums.size();
int max=nums[0],sum=nums[0];
for(int i=1;i<n;i++){
sum=((sum<0)?0:sum)+nums[i];
max=sum>max?sum:max;
}
return max;
}``````

• @cbmbbz this can go wrong if there is only one negative number in the array.

• ``````    public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
sum = Math.max(sum + nums[i], nums[i]);
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
``````

• This post is deleted!

• ``````public int maxSubArray(int[] nums) {

int n = nums.length;
int max = nums[0];
int sum = nums[0];
int i = 1;

while (i < n) {
sum = Math.max(sum, 0);
max = Math.max(sum + nums[i], max);
i++;
}

return max;
}``````

• nice solution~~~

• When found a potential subarray, maxEndingHere is not cleaned, so it won't count right for second potential subarray, for example in this test case -2,1,-3,4,-1,2,1,-5,4,1,2,1,4, your program will output 13 which contains 1 from history.

• interesting fact: a problem solved by a computer professor in 1984, now become an easy level problem in Leetcode in 2016/2017...

• This post is deleted!

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.