1. 题目
2. 读题(需要重点注意的东西)
思路(动态规划):
因为方程只与f[i-1]有关,所以不需要开数组,只需要用一个变量记录一下f[i-1]即可。
3. 解法
---------------------------------------------------解法---------------------------------------------------:
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
for(int i = 0,last = 0;i < nums.length;i++){
last = nums[i] + Math.max(0,last);
res = Math.max(last,res);
}
return res;
}
}
可能存在的问题:
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
- dp