解题思路

这是一个经典的动态规划问题。我们可以用以下思路解决：

  1. 定义 表示以第i个数字结尾的最长上升子序列的长度
  2. 对于每个位置 ，遍历它前面的所有位置
  3. 如果 ，说明可以将 接在以 结尾的上升子序列后面
  4. 状态转移方程： 其中 且
  5. 最终答案为 数组中的最大值

代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    vector<int> dp(n, 1);  // 初始化dp数组，每个元素至少是长度为1的子序列
    int maxLen = 1;
    
    for(int i = 1; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    cout << maxLen << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 初始化dp数组
        int maxLen = 1;
        
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        
        System.out.println(maxLen);
    }
}

n = int(input())
arr = list(map(int, input().split()))

dp = [1] * n  # 初始化dp数组

for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j] + 1)

print(max(dp))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： - 两层嵌套循环
  • 空间复杂度： - 需要一个长度为 的 数组