C language force deduction question 53 of the largest subarray sum. Dynamic programming and divide and conquer

Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .

Subarray Is a continuous part of the array .

Example 1：

Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .

Example 2：

Input ：nums = [1]
Output ：1

Example 3：

Input ：nums = [5,4,-1,7,8]
Output ：23

Tips ：

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

Advanced ： If you have implemented complexity as O(n) Solution method , Try something more subtle Divide and conquer method solve .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/maximum-subarray
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Method 1 ： Dynamic programming

In fact, this question can be thought of like this ：
1. If it's all negative numbers , That is to find the maximum value , Because negative numbers must be bigger and bigger .
2. If there is a positive number , It must start with a positive number and , Otherwise, there is a negative value ahead , And must be getting smaller , So start with a positive number .
3. When sum is less than zero , This interval is over , Then start again with the next positive number ( That is to return to 2 了 ). and dp It is reflected in this place .

The of dynamic programming is to traverse the array first , The sum of the current maximum continuous subsequences is sum, The result is ans
If sum > 0, shows sum It has a gain effect on the results , be sum Keep and add the current traversal number
If sum <= 0, shows sum There is no gain effect on the results , Need to give up , be sum Update directly to the current traversal number
Every comparison sum and ans Size , Set the maximum value to ans, The end of traversal returns the result
Time complexity ：O(n)

Method 2 ： Divide and conquer method

The idea of divide and conquer is like this , In fact, it is also classified discussion .

The maximum sum of continuous subsequences is mainly obtained from the maximum sum of elements in these three molecular intervals ：

    The first 1 part ： Subinterval [left, mid];
    The first 2 part ： Subinterval [mid + 1, right];
    The first 3 part ： Contains subintervals [mid , mid + 1] Subinterval of , namely nums[mid] And nums[mid + 1] It must be chosen .

It is enough to find the maximum value of these three parts .

explain ： Consider the 3 When a continuous subarray partially spans two intervals , because nums[mid] And nums[mid + 1] It must be chosen , It can spread from the middle to both sides , Spread to the end Select the maximum ,

The following is the code of dynamic programming ：

int maxSubArray(int* nums, int numsSize) {
    int pre = 0, maxAns = nums[0];
    for (int i = 0; i < numsSize; i++) {
        pre = fmax(pre + nums[i], nums[i]);
        maxAns = fmax(maxAns, pre);
    }
    return maxAns;
}