Leetcode 53. Maximal suborder and dynamic programming solutions, greedy methods, and dichotomies

The title

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example:

Input: [– 2, 1, 3, 4, 1, 2, 1, 5, 4] output: 6: continuous subarray and maximum of [4, 1, 2, 1], is 6.

Step up: If you already have an O(n) solution, try a more sophisticated divide-and-conquer solution.

Dynamic programming solution

Greedy method

Local optimal: discard the continuous sum when it is negative and clear the sum. Recalculate the continuous sum from the next element. Because the negative number plus the next element, the continuous sum gets smaller and smaller

Global optimization: Select the largest continuous sum and record the continuous sum of each time and compare with the previous largest continuous sum, take the largest value to save the code:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        int sum = 0;
        int result = INT_MIN;
        for(int i = 0; i<nums.size(a); i++) { sum += nums[i];if(sum > result)
                result = sum;
            if(sum<=0) sum = 0;
        }
        returnresult; }};Copy the code

dichotomy