8ms C++ DP solution


  • 1
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        if(n<1)return 0;
        int *dp=new int[n];
        int maxsum=nums[0];
        dp[0]=nums[0];
        for(int i=1;i<n;i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            maxsum=max(maxsum,dp[i]);
        }
        delete[] dp;
        return maxsum;
    }

  • 0
    P

    Thank you for the solution. Based on your solution, I have changed it to this o(1) space solution:

    class Solution {
    public:
    int maxSubArray(vector<int>& nums) {
    int maxsum;
    int dpCurrent, dpNext;

        if (nums.size() < 1) return 0;
        maxsum = nums[0];
        dpCurrent = nums[0];
        
        for (int i = 1; i < nums.size(); ++i){
            dpNext = max(dpCurrent + nums[i], nums[i]);
            maxsum = max(dpNext, maxsum);
            dpCurrent = dpNext;
        }
        return maxsum;
        
    }
    

    };


Log in to reply
 

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