【題目敘述】https://vjudge.net/problem/HDU-1087
【解題想法】DP
- 題目要求從start-point（分數最小）往end-point（分數最大）跳，每次都只能跳往分數更高的棋子。
- mx[i]：跳到第 i 顆棋子時，累計的最高分數。
- 狀態轉移方程：
- 跳到第 i 顆棋子之前，可以經由第 j 顆棋子（0 <= j < i）
- 如果 a[j] < a[i]，mx[i] = max(mx[i], mx[j] + a[i]);
#include <iostream>
using namespace std;
int n, a[1005], mx[1005], ans;
int main() {
while (cin >> n){
if (n == 0) break;
ans = 0;
for (int i = 0; i < n; i++){
cin >> a[i];
mx[i] = a[i];
for (int j = 0; j < i; j++){
if (a[i] > a[j]) mx[i] = max(mx[i], mx[j] + a[i]);
}
ans = max(ans, mx[i]);
}
cout << ans << "\n";
}
}