https://leetcode.com/problems/maximum-subarray/description/
解题思路：
- 首先确定其是动态规划（最有子结构，重叠子问题，无后效性）
- 比较当前index的值和当前index值+index-1的sum值，其最大值为当前index的sum值，最后比较所有sum值得到最大子数组的值
代码如下：
class Solution {
public int maxSubArray(int[] nums) {
int len = nums.length;
if(len == 1) return nums[0];
int[] dp = new int[len];
dp[0] = nums[0];
int max = dp[0];
for(int i = 1; i < len; i++){
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
max = Math.max(dp[i], max);
}
return max;
}
}
网友评论