分析：

題意就是，在一個數組里找遞增的子序列的最大和，而且子序列元素可以不相鄰。
我先上一個錯誤代碼，這是我剛看完題后一分鐘就寫的，事實上沒想象中簡單，等會我分析一下錯誤原因

#include<iostream> #include<algorithm> #include<cmath> using namespace std; int a[1001]; int m[1001]; int main(){int n,i,j;while(cin>>n){if(n==0) return 0;for(i=1;i<=n;++i){cin>>a[i]; //把數存到數組里}m[1]=a[1];for(i=2;i<=n;++i){m[i]=a[i];//m[i]是以第i個數為結尾的最大和//這里先初始化，因為m[i]最小就是a[i]，所以把初始值定為a[i]。for(j=i-1;j>=1;--j){if(a[j]<a[i]&&a[j]>0){//如果i之前，有比a[i]小的數a[j]，就把他的m[j]加到m[i]上m[i]+=m[j];break;}}}cout<<*max_element(m+1,m+n+1)<<endl;}}

錯誤原因：

我以為如果a[i]大于a[i-1]，那a[i]+m[i-1]就是m[i]了，事實上，也許i之前有更大的m，他加上a[i]后，會大于a[i]+m[i-1]。那，我現在就需要找出i之前最大的m，讓他加上a[i]不就好了

ac答案

短暫的思考了一分鐘，我寫出了下面的代碼，然后就AC了

#include<iostream> #include<algorithm> #include<cmath> using namespace std; int a[1001]; int m[1000]; int main(){int n,i,j,ma;while(cin>>n){if(n==0) return 0;for(i=1;i<=n;++i){cin>>a[i]; }m[1]=a[1];for(i=2;i<=n;++i){m[i]=a[i];ma=0;//由于a[i]在變，所以每次最大值都不一樣，需要重新遍歷，先把ma初始化一下for(j=1;j<=i-1;++j){//從1開始，還是從i-1開始，都一樣，因為我都需要全部遍歷一遍，才能找到最大的m[j]，這里我用ma存那個最大值if(a[j]<a[i]){//a[j]比a[i]小，那么m[i]=a[i]+m[j] 用ma存m[j]if(ma<m[j] ) ma=m[j];//循環完之后，ma存的是所有 m[j]中最大的 }}m[i]=a[i]+ma;//加上a[i]就ok了}cout<<*max_element(m+1,m+n+1)<<endl;//找數組m中最大的元素}}

總結

以上是生活随笔為你收集整理的深入剖析：Super Jumping! Jumping! Jumping! (动规)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。