首页 > 其他 > 详细

pat甲级1007 Maximum Subsequence Sum

时间:2020-08-07 09:41:40      阅读:75      评论:0      收藏:0      [点我收藏+]

题意:给你k个数字组成一个串,要求这个串中子串可以得到的最大的值,注意是子串而不是子序列,子序列可以不连在一起,子串必须是连续的一个串。同时还要求最大的子串的开头和结尾(左右值)的值是多少。如果k个数字都是负数,则输出0,和整个串的开头和结尾的值。

分析:动态规划的入门题,可以这样思考,从前往后扫一遍,如果当前的数字+前面的一个子串构成的值>当前数字,那说明你得到前面这个子串肯定是赚的呀,那就收下,连在一起,同时更新一下左右值,左值应该是前面这个子串的左值,右值就是当前数字呗。如果在合并之后得到的值比我们之前得到的最大值大,更新最大值就好了。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 int a[100010];
 6 int dp[100010];
 7 int main()
 8 {
 9     int n;
10     while(cin>>n)
11     {
12         for(int i=0;i<n;i++)
13         {
14             cin>>a[i];
15             dp[i]=a[i];
16         }
17         int l=a[0],r=a[0],maxx=a[0],al=a[0];
18         for(int i=1;i<n;i++)
19         {
20             if(dp[i-1]+a[i]>dp[i])
21             {
22                 dp[i]=dp[i-1]+a[i];
23             }
24             else
25             {
26                 l=a[i];
27             }
28             if(dp[i]>maxx)
29             {
30                 maxx=dp[i];
31                 r=a[i];
32                 al=l;
33             }
34         }
35         if(maxx<0)
36         {
37             cout<<"0"<<" "<<a[0]<<" "<<a[n-1]<<endl;
38             continue;
39         }
40         else
41         {
42             cout<<maxx<<" "<<al<<" "<<r<<endl;
43         }
44     }
45     return 0;
46 }

 

pat甲级1007 Maximum Subsequence Sum

原文:https://www.cnblogs.com/wade1998/p/13449972.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!