C++ Dynamic Programming Solution with comments. Any suggestion welcomes!


  • 1
    S
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int n=nums.size();
            if(n==1)
            return nums[0];
            vector<int> result(n,INT_MIN);//save the maximal continous sum when including nums[i]
            result[0]=nums[0];
            int Max=result[0];
            for(int i=1;i<n;++i)
            {
                if(result[i-1]<0)//no contribution
                result[i]=nums[i];//restart
                else
                result[i]=result[i-1]+nums[i];//add this number to the running sum
                Max=max(Max,result[i]);// update global max
        }
        return Max;
        }
    };

Log in to reply
 

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