leetcode 53. Maximum subarray maximum subarray sum (medium)

One 、 The main idea of the topic

label :  Dynamic programming

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 .

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 .

Two 、 Their thinking

Define a max Save the largest subarray and , It is also the return result , Define a dp[i], Used to indicate that i The maximum array sum of arrays with elements ending . The equation of state transfer is ：dp[i] = max(dp[i-1]+nums[i], nums[i])

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int maxSubArray(int[] nums) {
 int n = nums.length;
 int[] dp = new int[n];
 dp[0] = nums[0];
 int max = dp[0];
 for (int i = 1; i < n; i++) {
 dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
 max = Math.max(dp[i], max);
 }
 return max;
 }
}


Four 、 Summary notes

• 2022/7/6  Do programmers also have “ scholars scorn each other ” What's wrong with