題目描述：

一個數(shù)的序列bi，當(dāng)b1 < b2 < ... < bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1, a2, ...,aN)，我們可以得到一些上升的子序列(ai1, ai2, ..., aiK)，這里1 <= i1 < i2 < ... < iK <= N。比如，對于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中序列和最大為18，為子序列(1, 3, 5, 9)的和.

你的任務(wù)，就是對于給定的序列，求出最大上升子序列和。注意，最長的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和為100，而最長上升子序列為(1, 2, 3)。

輸入：                       

輸入包含多組測試數(shù)據(jù)。 每組測試數(shù)據(jù)由兩行組成。第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000（可能重復(fù)）。

輸出：                       

對于每組測試數(shù)據(jù)，輸出其最大上升子序列和。

樣例輸入：                       

7

1 7 3 5 9 4 8

樣例輸出：                       

18

這道題本來不是什么難題，只需用一個sum[]來記錄每一個位置的最大上升和，每回找前面一個比當(dāng)前元素小且最大的sum[]相加求出當(dāng)前位置的最大上升和。
但一開始我想當(dāng)然的認(rèn)為離的當(dāng)前元素最近的小值即為所求元素，還用了一個數(shù)組來記錄，導(dǎo)致問題過于復(fù)雜。
后來終于用最簡單的辦法做了出來，但要注意它這個是嚴(yán)格上升的子序列。

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #define MAX 1005

 int sum[MAX];

 int num[MAX];

 //1 2 3 4 5 6 7

 //1 7 3 5 9 4 8

 //0 1 1 3 4 3 6

 //1 8 4 9 18 7 15

 //0 5 2 3 1 0 2 4 5 8

 //5 4 8 2 5 7 5 6

 int main(int argc, char const *argv[])

 {

     int n;

     while(scanf("%d",&n) != EOF) {

         int max = ;

         for(int i = ; i <= n; i++) {

             scanf("%d",&num[i]);

         }

         sum[] = num[];

         for(int i = ; i <=n; i++) {

             int maxTemp = num[i];

             for(int j = i - ; j >= ; j--) {

                 if(num[i] > num[j]) {

                     int temp = sum[j] + num[i];

                     if(maxTemp < temp) {

                         maxTemp = temp;

                     }

                 }

             }

             sum[i] = maxTemp;

             if(max < maxTemp) {

                 max = maxTemp;

             }

         }

         /*for(int i = 1; i <= n; i++) {

             printf("%d\t",sum[i]);

         }*/

         printf("%d\n", max);

     }

     //system("pause");

     return ;

 }

總結(jié)

以上是生活随笔為你收集整理的九度oj 1480的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。