https://leetcode.cn/problems/maximum-subarray/
dp
-
本题旨在求最值,可以考虑使用dp
-
dp难点在于如何确定状态及状态转移
-
我们可以利用数学归纳的思想(如何利用dp[0…i-1]推导出dp[i])
-
那首先要明确dp[i]是什么含义,这里可以先考虑将dp[i]直接理解为前i个子数组的最大子串和,这样定义状态时,此时dp[i]进行返回就是所求结果吗?
或者可以问自己:这样定义状态可以得到合适的状态转移方程吗?
答案是否定的;因为我们无法保证nums[0…i]的最大子数组和与nums[i+1]相邻,所以我们无法由dp[i]推出dp[i+1],所以无法进行数学归纳
-
那这里就要尝试换一种状态,我们可以将dp[i]定义为以nums[i]为最大子数组的结尾元素,求得的最大子数组之和,就是dp[i]
此时规避了2中不相邻的情况,所以可以尝试使用
-
-
明确base case:dp[i]仅由nums[i]组成时,dp[i]=nums[i]
-
给出代码:
class Solution {
public int maxSubArray(int[] nums) {
if(nums==null||nums.length==0) return 0;
int[] dp = new int[nums.length];
//2:
for(int i=0;i<dp.length;i++){
dp[i]=nums[i];
}
for(int i=1;i<dp.length;i++){
dp[i]=Math.max(dp[i],dp[i-1]+nums[i]);
}
int res=dp[0];
for(int i=0;i<dp.length;i++){
if(dp[i]>res){
res=dp[i];
}
}
return res;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)