动态规划 1235: 最大连续子序列
动态规划 1235: 最大连续子序列
1944864971 发表于2年前
动态规划 1235: 最大连续子序列
  • 发表于 2年前
  • 阅读 4
  • 收藏 0
  • 点赞 0
  • 评论 0

移动开发云端新模式探索实践 >>>   

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int n;
while(scanf("%d",&n)&&n)
{
int arry[n],dp[n];
for(int i=0; i<n; i++)
scanf("%d",&arry[i]);
dp[0]=arry[0];
int max1=arry[0],end1=0,start=0,start1=0;
for(int i=1; i<n; i++)
{
dp[i]=max(dp[i-1]+arry[i],arry[i]);//动态转移方程
if( dp[i-1]+arry[i]<arry[i])start=i;//如果当前子序列的和小于当前值时更新起点位置不能用(dp[i]==arry[i])可能会有dp[i-1]+arry[i]==arry[i]的情况
if(max1<dp[i])
{
max1=dp[i];//获取最大的子序列和
end1=i;//更新末尾位置
start1=start;//更新起点位置!!!!注意这点,此时也要更新否则错误
}
}
if(max1>=0)
printf("%d %d %d\n",max1,arry[start1],arry[end1]);
else printf("0 %d %d\n", arry[0],arry[n-1]);
}
return 0;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: