2010-5-25 Maximum Sum

Maximum Sum
 
오늘은 좀 심심해서 주드 온라인으로 달려가서 문제를 풀었는데, 선택한 제목은 다음과 같다.

Maximum Sum

Time Limit: 15 Sec  Memory Limit: 128 MB Submissions: 523  Solved: 41

Description

Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example, 4, 2, 1, 5, 3 in this subsequence a few possible increasing subsequences are 1) 4 2) 2 3) 1 4) 5 5) 3 6) 4, 5 7) 2, 5 8) 2, 3 9) 1, 5 10) 1, 3 but 4, 5 gievs the maximum sum. Your task is how to find such the maximum sum in a given integer array.

Input

Multiply Cases, For each case: The first line contains N(0< N <=1000000), which is the number of the integer array. The second line contains N integer numbers not exceeding 2000000 by the absolute value.

Output

For each case, output only one integer, which is the maximum sum of increasing subsequences.

Sample Input

5



4 2 1 5 3

Sample Output

9























 ， ， ， ，   ， ， ：







#include <stdio.h>



#define N 1000000



int main(){



   int n = 0, i = 0, j = 0;

   int data[N], rec[N], tmp = 0, max, maxn;

   

    scanf("%d", &n);



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

      

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

      rec[i] = data[i];

    }



    max = rec[0];

    maxn = 0;



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

       for(j = i -1 ; j >= 0; j --){

          if(data[j] < data[i]){

             if(j == maxn){      

               rec[i] = max + data[i];

               max = rec[i];

               maxn = i;

               goto out;

             }

             else{

                 if((tmp = rec[j] + data[i]) > rec[i]){

                    rec[i] = tmp;

                 }

             }

          }

      }



       if(rec[i] > max){

          max = rec[i];

          maxn = i;

       }

out:  ;

    }



   printf("%d", max);



    return 0;

}











 ， ！