[dynamic programming simple question] leetcode 53. maximum subarray and

LeetCode 53. Maximum subarray and

I'm not autistic ！ Come on ！
https://leetcode.cn/problems/maximum-subarray/
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 .

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 .

Input ：nums = [1]
Output ：1

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

Refer to this up Solution method
https://www.bilibili.com/video/BV1XR4y1j7Lo/
Five steps for topic analysis

1. Design status

dp[i] Says to the first i The largest subarray and .

By the end of i The subarray ending with an integer is divided into two cases ：

• And the i-1 A sub array ending in an integer
• A separate By the end of i An integer as a subarray

give an example ：[1, -3, 2]

• With -3 Is the ending subarray, and the maximum subarray sum is max(1+(-3), -3) = -2
• With 2 Is the ending subarray, and the maximum subarray sum is max((1+(-3)+2), 2) = 2

2. Write the equation of state transition

dp[i] = max(dp[i-1]+nums[i], nums[i])

3. Set the initial state

dp[0] = nums[0]

4. Perform state transition

5. Return to the final solution

Solution

//  Taking the maximum 
int max(int a, int b) {
    
    return a > b ? a : b;
}

int maxSubArray(int* nums, int numsSize){
    
    int dp[100001];
    //  The initial state 
    dp[0] = nums[0];
    int maxValue = nums[0];
    for(int i = 1; i < numsSize; ++i) {
    
	    //  Perform state transition 
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        maxValue = max(dp[i], maxValue);
    }
    //  Return to the final solution 
    return maxValue;
}

Solution(Python)

Use Python Realizing the rotation method is simpler

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        pre, max_value = 0, nums[0]
        for value in nums:
            pre = max(pre + value, value)
            max_value = max(max_value, pre)
        return max_value