Solution by Zegang Cheng


  • 0
    C

    C++ solution using DP:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
    
            // initialization
            int size = nums.size();
            int dp[size];
            dp[0] = nums[0];
            int maxsum = nums[0];
    
            for(int i = 0; i < size - 1; i++) {
    
                // record the max sum of the continuous substring that ends at nums[i]
                dp[i + 1] = max(dp[i] + nums[i + 1], nums[i + 1]);
                // record the maximum
                if(maxsum < dp[i + 1]) maxsum = dp[i + 1];
            } 
    
            return maxsum;
        }
    };
    

Log in to reply
 

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