信息學奧賽一本通（C++版）在線評測系統
基礎算法 第一節 動態規劃的基本模型
1285：最大上升子序列和

---

“最大上升子序列和”問題課堂講解

1. 理解題意

同學們，想象我們有一串數字，就像一串彩色的珠子，每個珠子上都標著一個數字，這就是題目里說的序列。比如有這樣一串數字：(1)，(7)，(3)，(5)，(9)，(4)，(8)。

現在我們要從這串數字里挑出一些數字，這些數字要滿足后面的數字比前面的數字大，這樣挑出來的數字組成的新序列就叫上升子序列。比如說從上面那串數字里挑出(1)，(3)，(5)，(9)，這就是一個上升子序列。

我們的任務是在所有能挑出來的上升子序列里，找到數字加起來和最大的那個上升子序列，然后把這個最大的和告訴大家。要注意哦，最長的上升子序列，它的數字和不一定是最大的。就像數字序列(100)，(1)，(2)，(3)，最長的上升子序列是(1)，(2)，(3)，但是數字和最大的上升子序列是(100)，因為(100)比(1 + 2 + 3)的和要大。

2. 解題思路

我們可以用一種像搭積木一樣的方法來解決這個問題，這種方法叫動態規劃。

我們先給每個數字都想象有一個“小背包”，這個“小背包”里裝著以這個數字結尾的最大上升子序列的和。一開始，每個數字自己就是一個長度為(1)的上升子序列，所以每個數字“小背包”里的和就是它自己的值。

然后呢，我們從第二個數字開始，一個一個地看。對于每個數字，我們回頭看看它前面的那些數字。要是前面有個數字比它小，那就說明可以把這個小的數字和當前數字連起來，形成一個新的上升子序列。我們就把前面那個小數字“小背包”里的和，加上當前數字，得到一個新的和。我們比較一下，是原來這個數字“小背包”里的和大，還是新得到的和大，把大的那個存到當前數字的“小背包”里。

最后，我們看看所有數字的“小背包”，找出里面最大的那個和，這個和就是我們要找的最大上升子序列的和啦。

3. 解題步驟

1. 輸入數字序列：我們要先知道這串數字有多少個，也就是輸入序列的長度(N)。然后把這串數字里的每個數字都一個一個地記下來，存到一個數組里。
2. 初始化“小背包”：讓每個數字的“小背包”（也就是存儲以該數字結尾的最大上升子序列和的數組）里都先裝上它自己的值，因為每個數字自己就是長度為(1)的上升子序列，和就是它本身。
3. 更新“小背包”：從第二個數字開始，一個一個地看，對于每個數字，看看它前面比它小的數字，把前面小數字“小背包”里的和加上當前數字，和原來當前數字“小背包”里的和比較，把大的那個存到當前數字的“小背包”里。
4. 找出最大和：看看所有數字的“小背包”，找出里面最大的那個和，這就是我們要的答案。

4. C++代碼實現

#include <iostream> // 包含輸入輸出流的頭文件，這樣我們就能從鍵盤輸入數字，把結果輸出到屏幕上啦
using namespace std; int main() {int n; // 定義一個變量 n，用來存數字序列里有多少個數字cin >> n; // 從鍵盤輸入數字的個數，存到 n 里int a[1005]; // 定義一個數組 a，用來存數字序列，最多能存 1005 個數字int dp[1005]; // 定義一個數組 dp，這就是我們說的“小背包”數組，用來存以每個數字結尾的最大上升子序列的和// 輸入數字序列，并初始化“小背包”for (int i = 1; i <= n; i++) {cin >> a[i]; // 從鍵盤輸入一個數字，存到數組 a 的第 i 個位置dp[i] = a[i]; // 把“小背包”數組 dp 的第 i 個位置初始化為當前數字 a[i]}// 更新“小背包”for (int i = 2; i <= n; i++) { // 從第二個數字開始看for (int j = 1; j < i; j++) { // 看看當前數字前面的所有數字if (a[j] < a[i]) { // 如果前面的數字 a[j] 比當前數字 a[i] 小// 比較 dp[i] 和 dp[j] + a[i] 的大小，把大的那個存到 dp[i] 里dp[i] = max(dp[i], dp[j] + a[i]);  }}}int ans = 0; // 定義一個變量 ans，用來存最大上升子序列的和，先初始化為 0// 找出“小背包”數組里的最大值for (int i = 1; i <= n; i++) {ans = max(ans, dp[i]); // 比較 ans 和 dp[i] 的大小，把大的那個存到 ans 里}cout << ans << endl; // 把最大上升子序列的和輸出到屏幕上return 0;
}

5. 知識點總結

1. 數組：我們用了兩個數組，(a)數組存原始的數字序列，(dp)數組存每個數字對應的“小背包”里的和。數組就像一個小抽屜，我們可以把很多東西（這里是數字）一個一個地放進去，還能按照順序找到它們。
2. 循環：循環就像一個勤勞的小工人，會按照我們的要求重復做一些事情。這里用了兩層循環，外層循環一個一個地看數字，內層循環回頭看前面的數字，這樣就能更新每個數字的“小背包”啦。
3. 動態規劃：這是一種很厲害的解題方法，把大問題分成很多小問題，先解決小問題，再從這些小問題的答案里找到大問題的答案。在這個問題里，我們先算出每個數字對應的最大上升子序列的和，再從這些和里找出最大的，就是整個序列的最大上升子序列的和啦。
4. 比較大小：用(max)函數來比較兩個數的大小，找出大的那個數。這樣就能更新“小背包”里的和以及最終的最大和答案啦。