求问maxSubArray的DP解法

题目：
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

样例：
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6

我的思路是设f[i]表示 原数组中 0-i 的最大子序列和，假定f[j]存在，则如果i-j的和大于零则更新f[i]，自己写完了也是感觉有问题但是没检查出来，最近刚看的DP，希望哪位大神能指点下，谢谢了！

1. public static int maxSubArray(ArrayList<Integer> nums) {
   
2.         
   
3.                 int[] f = new int[nums.size()];
   
4.                 f[0]  = nums.get(0);
   
5.                 int sum = 0;
   
6.                 for(int i = 1; i < nums.size(); i++){
   
7.                         for(int j = 0; j < i; j++){
   
8.                                 f[i] =  Math.max(f[j] + add(nums,j+1,i), f[j]);
   
9.                         }
   
10.                
    
11.                         if(f[i] > sum){
    
12.                                 sum = f[i];
    
13.                         }
    
14.                        
    
15.                 }
    
16.                
    
17.                 return sum;
    
18.     }
    
19. 
    
20.         public static int add(ArrayList<Integer> nums,int start, int end){       
    
21.                 int sum = 0;
    
22.                 for(int i = start; i <= end; i++){
    
23.                         sum = sum + nums.get(i);
    
24.                 }
    
25.                
    
26.                 return sum;
    
27.         }

复制代码

你应将 f ( i ） 定义为 "以 i 结尾的子数组可能得到的最大和"。这样，状态方程就是
f ( i ) = max ( f (i - 1 ) + A( i ) , A ( i ))

因为f ( i )仅依赖于f ( i - 1 )，所以也没有必要维护 f ( i ) 这个数组。用一个变量记录上一次的 f 值即可。

stellari 发表于 2015-6-29 21:00
你应将 f ( i ） 定义为 "以 i 结尾的子数组可能得到的最大和"。这样，状态方程就是
f ( i ) = max ( f (i ...

非常感谢！想再请教下，想这种状态方程的思路是如何呢？

if(dp[i-1] < 0 || dp[i-1] + nums[i] < 0)
    dp[i] = nums[i];
else
    dp[i] = dp[i-1] + nums[i];

lvbxr 发表于 2015-6-30 11:55
if(dp < 0 || dp + nums < 0)
    dp = nums;
else

if的第二个条件不太对吧？如果能执行到这个条件，说明必有dp(i-1) >= 0，如果是这样，无论nums(i)的值是多少，肯定有个dp(i-1) + nums(i) >= nums(i)，所以dp(i)不应该取nums(i)，而应该取 dp(i-1) + nums(i). 事实上，这第二个条件没有必要写的。