preface

In fact, the official also provides a method of dynamic planning. I'll make it up when I'm free (cry)

One topic

Give you an integer array nums. Please find a continuous sub array with the largest sum (the sub array contains at least one element) and return its maximum sum. A subarray is a contiguous part of an array.

II. Examples and tips

Example 1:

Input: num = [- 2,1, - 3,4, - 1,2,1, - 5,4]
Output: 6
Explanation: the maximum sum of continuous subarray [4, - 1,2,1] is 6.

Example 2:

Input: num = [1]
Output: 1

Example 3:

Input: num = [5,4, - 1,7,8]
Output: 23

Tips:

    1 <= nums.length <= 105
    -104 <= nums[i] <= 104

Advanced: if you have implemented a solution with complexity O(n), try using a more sophisticated divide and conquer method.

Three questions

1. Greed

The whole array needs to be traversed once, and the time complexity is O(n). Two variables are used to save the current sum and the maximum sum. Only constant space is used, and the space complexity is O(1).

Attach the messy ideas of writing the question at that time:

Core idea: if the sum before the currently traversed element is less than 0, the previous sequence will be discarded directly.

The code is as follows:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max = nums[0];
        int curSum = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(curSum >= 0)
            {
                curSum += nums[i];
            }else{
                curSum = nums[i];
            }
            if(curSum > max)
            {
                max = curSum;
            }
        }
        return max;
    }
};

be careful:

1.max must take num [0], not 0, because the largest number in num may be negative.

2. The judgment statement of cursum > max should be placed last, because when num [0] < 0, max will be directly updated to 0, which violates the first article

2. Divide and conquer strategy

The divide and conquer strategy is to decompose the problem into multiple sub problems, and then decompose the sub problems into sub problems... And these sub problems are independent of each other and have the same or similar form with the original problem. After solving these sub problems recursively, the solutions of each sub problem are combined to obtain the solution of the original problem.

For example, the divide and conquer strategies involved in sorting algorithm include dichotomy, fast sorting and Hill sorting.

Idea:

The steps of divide and conquer strategy are usually the following three steps:

Decomposition: decompose the original problem into several small-scale, independent sub problems with the same form as the original problem;

Solution: if the subproblem is small and easy to be solved, solve it directly, otherwise [recursively] solve each subproblem;

Merge: merge the solutions of each sub problem into the solutions of the original problem.

Returning to the original question, the interval (l,r) can be decomposed into left (l,m) and right (m+1,r), and then the two intervals can be continuously divided into subproblems with small enough scale to obtain the direct solution... Therefore, the recursive termination can be found, that is, the condition that can not be further divided is: when the interval length is 1, left==right. At the same time, for (l,r), the sum of the largest subarray may happen to be in the left interval, or in the right interval, or even in the second half of the left interval + the first half of the right interval. Therefore, its occurrence can be roughly divided into two types:

        1. Across the midpoint m. → ③ take the middle point as the starting point, and extend forward, backward, left and right sections to find out

        2. Do not cross m. → find the maximum subarray sum of ① left / ② right interval

Finally, compare the three results and choose the largest one.

The code is as follows:

class Solution {
public:
    int findSpan(vector<int>& nums, int left, int right, int mid){
        int curSum = nums[mid];
        int leftSum = nums[mid], rightSum = nums[mid];
        for(int i = mid - 1; i >= left; i--)
        {
            curSum += nums[i];
            if(curSum > leftSum)
                leftSum = curSum;
        }
        curSum = nums[mid];
        for(int i = mid + 1; i <= right; i++)
        {
            curSum += nums[i];
            if(curSum > rightSum)
                rightSum = curSum;
        }

        return (leftSum + rightSum - nums[mid]);
    }

    int maxSum(vector<int>& nums, int left, int right){
        if(left == right)
        {
            return nums[left];
        }else{
            int mid = (left + right) / 2;
            int left_max,right_max,mid_max;
            left_max = maxSum(nums,left,mid);
            right_max = maxSum(nums,mid+1,right);
            mid_max = findSpan(nums,left,right,mid);
            return max(mid_max,max(left_max,right_max));
        }
    }

    int maxSubArray(vector<int>& nums) {
        return maxSum(nums,0,nums.size()-1);
    }
};