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
