題目1480：最大上升子序列和時間限制：1 秒 內存限制：128 兆 特殊判題：否 提交：562 解決：175 題目描述： 一個數的序列bi，當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)的和. 你的任務，就是對於給定的序列，求出最大上升子序列和。注意，最長的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和為100，而最長上升子序列為(1, 2, 3)。 輸入： 輸入包含多組測試數據。 每組測試數據由兩行組成。第一行是序列的長度N (1 <= N <= 1000)。第二行給出序列中的N個整數，這些整數的取值范圍都在0到10000（可能重復）。 輸出： 對於每組測試數據，輸出其最大上升子序列和。 樣例輸入： 7 1 7 3 5 9 4 8樣例輸出： 18來源： 2012年北京大學計算機研究生機試真題 [cpp] /********************************* * 日期：2013-3-25 * 作者：SJF0115 * 題號: 題目1480：最大上升子序列和 * 來源：http://ac.jobdu.com/problem.php?pid=1480 * 結果：AC * 來源：2012年北京大學計算機研究生機試真題 * 總結： **********************************/ #include<stdio.h> #include<string.h> int array[1010]; int Max[1010]; void LIS(int k){ memset(Max,0,sizeof(Max)); for(int i = 1;i <= k; i++){ Max[i] = array[i]; //和i號數據之前的數據比較 for(int j = 1;j < i;j++){ if(array[i] > array[j]){ if(Max[i] < Max[j] + array[i]){ Max[i] = Max[j] + array[i]; } } } } } int main() { int N,i; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); while(scanf("%d",&N)!=EOF){ //輸入數據 for(i = 1;i <= N;i++){ scanf("%d",&array[i]); } LIS(N); //輸出最大值 int MaxValue = -1; for(i = 1;i <= N;i++){ if(MaxValue < Max[i]){ MaxValue = Max[i]; } } printf("%d\n",MaxValue); } return 0; } /********************************* * 日期：2013-3-25 * 作者：SJF0115 * 題號: 題目1480：最大上升子序列和 * 來源：http://ac.jobdu.com/problem.php?pid=1480 * 結果：AC * 來源：2012年北京大學計算機研究生機試真題 * 總結： **********************************/ #include<stdio.h> #include<string.h> int array[1010]; int Max[1010]; void LIS(int k){ memset(Max,0,sizeof(Max)); for(int i = 1;i <= k; i++){ Max[i] = array[i]; //和i號數據之前的數據比較 for(int j = 1;j < i;j++){ if(array[i] > array[j]){ if(Max[i] < Max[j] + array[i]){ Max[i] = Max[j] + array[i]; } } } } } int main() { int N,i; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); while(scanf("%d",&N)!=EOF){ //輸入數據 for(i = 1;i <= N;i++){ scanf("%d",&array[i]); } LIS(N); //輸出最大值 int MaxValue = -1; for(i = 1;i <= N;i++){ if(MaxValue < Max[i]){ MaxValue = Max[i]; } } printf("%d\n",MaxValue); } return 0; }
