剑指offer连续子数组最大和
2021-03-30 03:26
标签：offer 算法 return 使用 subarray else lan 描述 最大和 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 使用动态规划，对于输入的数组nums[]，定义数组dp[nums.length]，并且dp[i]表示以num[i]为结尾的子数组的和的最大值，则状态转移方程为 则返回最大和为6，对应下标为3到6的子数组 剑指offer连续子数组最大和 标签：offer 算法 return 使用 subarray else lan 描述 最大和 原文地址：https://www.cnblogs.com/keke-coding/p/13587391.html题目描述
算法描述
* 如果dp[i-1]
* 如果dp[i-1]>0，那么可以将前面的数组纳入考量范畴，dp[i] = dp[i-1] + nums[i];
则最终返回的结果为dp[]数组中的最大值，并且对应的子数组为最大值向前直到不为0或负数的相对应的下标，例如
i
0
1
2
3
4
5
6
7
8
nums
-2
1
-3
4
-1
2
1
-5
4
dp
-2
1
-2
4
3
5
6
1
5
代码
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
int output = Integer.MIN_VALUE;
for(int i = 0;i