53. Maximum Subarray - cocoder39/coco39_LC GitHub Wiki

53. Maximum Subarray

Consider DP when solving this "max" problem. Then how to construct the DP? two ideas come in mind: 1 dp[i][j] is the max we can achieve from a subarray nums[i ... j]. 2 dp[i] is the max max we can achieve from a subarray nums[0 ... i].

for first idea, it hard to generate dp[i][j + 1] from dp[i][j] since there might be gap between the max subarray in [i .. j] and nums[j + 1] (if max subarray is not ending with nums[j])

for second idea, dp[i + 1] = nums[i] > 0 ? dp[i] + nums[i + 1] : dp[i]

Kadane's algorithm

int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size()); //dp[i] is maxSubArray that ends with nums[i]
        int res = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (i == 0) {
                dp[0] = nums[0];
            } else {
                dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i];
            }
            res = max(res, dp[i]);
        }
        return res;
    }

int maxSubArray(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        int endHere = nums[0], res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            endHere = max(endHere + nums[i], nums[i]);
            res = max(res, endHere);
        }
        return global;
    }

if we transfer the given array to a cumulative sum array, the problem is transferred to find out the start point and end point of a subarry from the sum array, which is equal to 121. Best Time to Buy and Sell Stock

int maxSubArray(vector<int>& nums) {
        vector<int> sums(nums.size());
        int res = INT_MIN;
        for (unsigned int i = 0; i < nums.size(); i++) {
            if (i == 0) {
                sums[0] = nums[0];
            } else {
                sums[i] = sums[i - 1] + nums[i];
            }
            res = max(res, sums[i]);
        }
        
        int low = sums[0];
        for (unsigned int i = 1; i < sums.size(); i++) {
            res = max(res, sums[i] - low);
            low = min(low, sums[i]);
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️