给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
子数组 是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入:nums = [1]
输出:1
示例 3:
输入:nums = [5,4,-1,7,8]
输出:23
作者:力扣 (LeetCode)
链接:https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn3cg3/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
//每一个节点的最大值
dp[0] = nums[0];
//最大值
int max = dp[0];
//[-2,1,-3,4,-1,2,1,-5,4]
for(int i = 1;i<len;i++){
//d[1]=1,d[2]=-2,d[3]=0
//d[4]=4,d[5]=3,d[6]=5
//d[7]=6,d[8]=1,d[9]=5
//负数重新计算
dp[i] = Math.max(dp[i-1],0) + nums[i];
//循环找到最大值
max = Math.max(dp[i],max);
}
return max;
}
}
标签:最大,示例,int,nums,LeetCode,数组,子序,dp
From: https://www.cnblogs.com/xiaochaofang/p/16826730.html