距离PAT考试还有13天,最重要的是做透每一题,以及捡起来贪心回溯动态规划的感觉
(1)思路
动态规划
sum的值为当前子串,maxsum的值为最大子串的值
maxsum=max(sum,maxsum);
需要思考的是如何保存最大子串的index
我们 设置三个变量 fir和last,以及b来保存
b为当前子串的开始,fir,last分别为最终子串的开始和结束
在遍历这个子串的过程中如果当前子串sum的值为负了,那么我们要舍弃当前的子串
因为无论后面怎样,这里的sum都会让后续的值变的更小,我们在sum小于零的时候
让其从新开始记录子串,即赋sum为0,并且令b等于此时的i+1,记录新的子串的起始位置
在sum非负的情况下我们比较当前子串和maxsum的值,如果maxsum更大那什么也不做
否则maxsum更新,此时把当前子串的开始b赋给fir即最终的子串的开始,由于last(最终子串)就是i
也等于当前子串的结束,这也是为什么不用一个变量e来保存结束位置的原因
#include <cstdio> #include <vector> using namespace std; int main() { int n; scanf("%d",&n); vector<int> v(n); int flag=0; for(int i=0;i<n;i++) { scanf("%d",&v[i]); if(v[i] >= 0) flag=1; } if(flag == 0) { printf("%d %d %d",0,v[0],v[n-1]); return 0; } int sum=0,maxsum=-1,b=0,last=n-1,fir=0; for(int i=0;i<n;i++) { sum+=v[i]; if(sum < 0) { sum=0; b=i+1; } else { if(sum > maxsum) { fir=b; last=i; maxsum=sum; } } } printf("%d %d %d",maxsum,v[fir],v[last]); return 0; }
这里暴力不能ac,注意子串包括一个元素的串
#include <cstdio> #include <climits> #include <vector> using namespace std; int main() { int n; scanf("%d",&n); vector<int> v; v.resize(n); const int inf=INT_MIN; int flag=0; for(int i=0;i<n;i++) { scanf("%d",&(v[i])); if(v[i] >= 0) flag=1; } if(flag == 0) { printf("%d %d %d",0,v[0],v[v.size()-1]); return 0; } int st=0,end=n-1,maxsum=inf; for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { //得从i开始不能是i+1 int sum=0; for(int k=i;k<=j;k++) { sum+=v[k]; } if(sum > maxsum) { maxsum=sum; st=i; end=j; } } } printf("%d %d %d",maxsum,v[st],v[end]); return 0; }
转载于:https://www.cnblogs.com/tclan126/p/8508511.html
相关资源：数据结构—成绩单生成器