当前位置：网站首页>Leetcode skimming -- bit by bit record 019

Leetcode skimming -- bit by bit record 019

2022-07-22 11:35:00 【Robust least squares support vector machine】

19. The finger of the sword Offer 42. The maximum sum of successive subarrays

requirement

Enter an integer array , One or more consecutive integers in an array form a subarray . Find the maximum sum of all subarrays .
The required time complexity is O(n).

Ideas

Dynamic programming ：

State definition ： Set up a dynamic programming list dp ,dp[i] Represented by elements nums[i] Is the maximum sum of consecutive subarrays at the end .
Transfer equation ： if dp[i-1]≤0 , explain dp[i - 1] Yes dp[i] Produce negative contribution , namely dp[i-1] + nums[i] Not so good nums[i] Itself big . if dp[i-1]＞0, explain dp[i - 1] Yes dp[i] Make a positive contribution .
The initial state ： dp[0] = nums[0], That is to nums[0] The maximum sum of consecutive subarrays at the end is nums[0].
Return value ： return dp The maximum value in the list , Represents the global maximum

Problem solving

#include <iostream>
using namespace std;
#include <vector>

class Solution {
    
public:
    int maxSubArray(vector<int>& nums) {
    
        vector<int> dp(nums.size(), 0);
        int max = nums[0];  //  Initialize the maximum subarray and , For the first element of the array 
        dp[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
    
            if (dp[i - 1] <= 0)
                dp[i] = nums[i];    // dp[i - 1] Less than or equal to 0, Negative contribution to subarray sum , So no need ＋
            else
                dp[i] = dp[i - 1] + nums[i]; // dp[i - 1] Greater than 0, Make a positive contribution to subarray and , So we need to ＋
            if (dp[i] > max) 
                max = dp[i];
        }
        return max;
    }
};


void test01()
{
    
    Solution soulution;
    vector<int> nums;
    nums.push_back(-2);
    nums.push_back(1);
    nums.push_back(-3);
    nums.push_back(4);
    nums.push_back(-1);
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(-5);
    nums.push_back(4);

    cout << soulution.maxSubArray(nums) << endl;
}

int main()
{
    
    test01();

    system("pause");
    return 0;
}