acwing 1016.最大上升子序列和
比如，对于序列(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。
第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。
输出格式
输出一个整数，表示最大上升子序列和。
数据范围
输入样例：
7 1 7 3 5 9 4 8
输出样例：
18
| 难度：简单 |
| 时/空限制：1s / 64MB |
| 总通过数：3427 |
| 总尝试数：4486 |
| 来源：《信息学奥赛一本通》 |
| 算法标签 |
c++代码
#include<iostream> #include<climits> using namespace std; int main() { int n; cin >> n; int a[n]; int dp[n]; for (int i = 0; i < n; i++) { cin >> a[i]; dp[i] = a[i]; } int maxn = INT_MIN; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] < a[i]) { dp[i] = max(dp[i],dp[j] + a[i]); } } maxn = max(maxn,dp[i]); } cout << maxn << endl; return 0; }
java代码
import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(reader.readLine()); int[] arr = new int[n]; int[] dp = new int[n]; String[] s = reader.readLine().split(" "); for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(s[i]); dp[i] = arr[i]; } int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = Math.max(dp[i],dp[j] + arr[i]); } } max = Math.max(dp[i],max); } writer.write(max + "\n"); writer.flush(); writer.close(); reader.close(); } }
