# Simplest and fastest O(n) C++ solution

• Idea is very simple. Basically, keep adding each integer to the sequence until the sum drops below 0.
If sum is negative, then should reset the sequence.

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

• So COOL!!!!!!!

• even i did in similar manner

``````class Solution {
public:
int maxSubArray(int A[], int n) {
if(n==0)
return 0;
int maxsum=A[0];
int runningsum=A[0];
for(int i=1;i<n;i++)
{
if((A[i]+runningsum)<A[i])
runningsum=A[i];
else
runningsum+=A[i];

if(runningsum>maxsum)
maxsum=runningsum;

}
return maxsum;
}
};``````

• 'sum' is kind of DP idea.

• better and easy!

• yes it is actually DP

• This post is deleted!

• Simpler than simplest :)

``````public class Solution {
public int maxSubArray(int[] A) {
int curMax = A[0], preMax = A[0];
for (int i = 1; i < A.length; i++){
preMax = Math.max(preMax+A[i], A[i]);
curMax = Math.max(curMax, preMax);
}
return curMax;
}
}``````

• can somebody explain this code ?
how is DP works?

• better and easy!

• ``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxsum = INT_MIN;
int tmp = 0;
for (int i = 0; i < nums.size(); ++i)
{
tmp += nums[i];
maxsum = max(maxsum, tmp);
if(tmp<=0) tmp = 0;
}
return maxsum;
}
};
``````

• This is the explanation to the OP's code.

Before explaining the original code, I'd like to introduce my version of the same algorithm, which is simpler for the readers to understand.

``````class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
else if (nums.size() == 1) return nums.at(0);

int int_local_max = nums.at(0), int_global_max = nums.at(0);
size_t sz_length  = nums.size();
for (size_t i = 1; i != sz_length; ++i) {
int_local_max  = max(int_local_max + nums.at(i), nums.at(i));
int_global_max = max(int_local_max, int_global_max);
}

return int_global_max;
}
};
``````

Apparently, this is an optimization problem, so DP is the one for choice.

When we are talking about DP, the first problem comes out to our mind should be: what's the statement of the sub-problem, whose format should satisfy that if we've solved a sub-problem, it would be helpful for solving the next-step sub-problem, and, thus, eventually helpful for solving the original problem.

Here is the sub-problem we state: denote `int_local_max[i]` as the max-sub-array-sum that ends with `nums[i]`. The relationship between the two steps is simple: `int_local_max[i + 1] = max (int_local_max[i] + nums[i + 1], nums[i + 1])` or `int_local_max[i + 1] = (int_local_max[i] > 0) ? int_local_max[i] + nums[i + 1] : nums[i + 1]`.

Now, all we have to do is to scan through the array, and find which `int_local_max[i]` is the maximum of all the `int_local_max`s.

In the OP's code, `ans` works like `int_global_max`, and

``````sum=max(sum,0); // prev step
sum+=A[i];
``````

works like `int_local_max = max(int_local_max + nums.at(i), nums.at(i));`. Hence, basically, the code uses DP algorithm, and `sum` in the code contains the sub-problem idea.

• I guess this will only work if there is a contiguous subarray that sums to positive but won't work on all inputs.

• good answer,but the "j" in `int ans=A[0],i,j,sum=0;` should not appear.

• Also, this solution causes a trouble for an empty array (A[0]). Below is my 5-liner with the updated C++ method signature.

``````    int maxSubArray(vector<int>& nums)
{
auto max_sum = INT_MIN, sum = 0;
for (auto n : nums)
{
sum = max(n, sum + n);
max_sum = max(max_sum, sum);
}

return max_sum;
}
``````

• @wael

I guess this will only work if there is a contiguous subarray that sums to positive but won't work on all inputs.

It works under any conditions.....

• @LiamHuang Thanks for your explanation!

• @LiamHuang Nice explanation!

• what if the inputs are all negative.

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