最长递增子序列的变形问题。
// runtime: 4ms // space; 496K #include <iostream> #include <cstdio> using namespace std; const int MAX = 1000; int arr[MAX]; int dp[MAX]; // 以arr[i]为结尾的最大上升子序列和 int MaxIncSubsequence(int k) { int sum = 0; for (int i = 0; i < k; ++i) { dp[i] = arr[i]; for (int j = 0; j < i; ++j) { if (arr[i] > arr[j]) { dp[i] = max(dp[i], dp[j] + arr[i]); } } sum = max(sum, dp[i]); } return sum; } int main() { int k; while (scanf("%d", &k) != EOF) { for (int i = 0; i < k; ++i) { scanf("%d", &arr[i]); } printf("%d\n", MaxIncSubsequence(k)); } return 0; }