Simplest and fastest O(n) C++ solution


  • 63
    L

    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;
        }
    };

  • 0
    A

    So COOL!!!!!!!


  • 2
    S

    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;
    }
     };

  • 2
    W

    'sum' is kind of DP idea.


  • 0
    A

    better and easy!


  • 0
    S

    yes it is actually DP


  • 0
    L
    This post is deleted!

  • 12
    A

    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;
        }
    }

  • 1
    Z

    can somebody explain this code ?
    how is DP works?


  • 0
    W

    better and easy!


  • 0
    H
    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;
        }
    };
    

  • 13
    L

    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_maxs.

    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.


  • 0
    L

    See my answer.


  • 0
    W

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


  • 0
    C

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


  • 3
    V

    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;
        }
    

  • 0
    D

    @wael

    @wael said in Simplest and fastest O(n) C++ solution:

    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.....


  • 0
    A

    @LiamHuang Thanks for your explanation!


  • 0
    K

    @LiamHuang Nice explanation!


  • 4
    U

    what if the inputs are all negative.


Log in to reply
 

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