一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 347|回复: 4
收起左侧

[Leetcode] 求问maxSubArray的DP解法

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-6-29 20:33:37 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

我的思路是设f表示 原数组中 0-i 的最大子序列和,假定f[j]存在,则如果i-j的和大于零则更新f,自己写完了也是感觉有问题但是没检查出来,最近刚看的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.         public static int add(ArrayList<Integer> nums,int start, int end){       
  20.                 int sum = 0;
  21.                 for(int i = start; i <= end; i++){
  22.                         sum = sum + nums.get(i);
  23.                 }
  24.                
  25.                 return sum;
  26.         }
复制代码
stellari 发表于 2015-6-29 21:00:20 | 显示全部楼层
你应将 f ( i ) 定义为 "以 i 结尾的子数组可能得到的最大和"。这样,状态方程就是
f ( i ) = max ( f (i - 1 ) + A( i ) , A ( i ))

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

使用道具 举报

 楼主| jy_121 发表于 2015-6-29 22:02:57 | 显示全部楼层
stellari 发表于 2015-6-29 21:00
你应将 f ( i ) 定义为 "以 i 结尾的子数组可能得到的最大和"。这样,状态方程就是
f ( i ) = max ( f (i ...

非常感谢!想再请教下,想这种状态方程的思路是如何呢?
回复 支持 反对

使用道具 举报

lvbxr 发表于 2015-6-30 11:55:44 | 显示全部楼层
if(dp[i-1] < 0 || dp[i-1] + nums[i] < 0)
    dp[i] = nums[i];
else
    dp[i] = dp[i-1] + nums[i];
回复 支持 反对

使用道具 举报

stellari 发表于 2015-6-30 12:24:31 | 显示全部楼层
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). 事实上,这第二个条件没有必要写的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表