申論題

提供一個C++的實現示例：
#include <iostream>
#include <vector>
using namespace std;

vector<int> findLongestIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> length(n, 1), sum(nums), prev(n, -1);
    int maxLength = 1, maxSum = nums[0], lastIndex = 0;

    // DP to compute length and sum of the longest increasing subsequence
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (length[j] + 1 > length[i] || (length[j] + 1 == length[i] && sum[j] + nums[i] > sum[i])) {
                    length[i] = length[j] + 1;
                    sum[i] = sum[j] + nums[i];
                    prev[i] = j;
                }
            }
        }
        if (length[i] > maxLength || (length[i] == maxLength && sum[i] > maxSum)) {
            maxLength = length[i];
            maxSum = sum[i];
            lastIndex = i;
        }
    }

    // Reconstruct the subsequence
    vector<int> lis;
    for (int i = lastIndex; i != -1; i = prev[i]) {
        lis.push_back(nums[i]);
    }
    reverse(lis.begin(), lis.end());
    return lis;
}

int main() {
    vector<int> nums = {9, 15, 7, 6, 11, 12, 4};
    vector<int> lis = findLongestIncreasingSubsequence(nums);
    for (int num : lis) {
        cout << num << " ";
    }
    return 0;
}
這段代碼首先使用動態規劃找出最長遞增子序列的長度和和，然後從這個子序列的最後一個元素開始，逆向追蹤以重建這個子序列。這樣不僅能找到長度最長的遞增子序列，當存在多個這樣的序列時，也能保證選出和最大的那一個。