题目描述

最长增长子列(LIS)

分析

典型动态规划问题,设dp[i]为以第i个数结尾的最长增长子列的长度，则:

\[\mathrm{dp}[i] = \max_{\mathop{0\leq k < i}\limits_{\mathrm{A}[i] > \mathrm{A}[k]}}\left \{\mathrm{dp}[k]+1 \right\}\]

初始时dp所有元素为1

实现

int lengthOfLIS(int* nums, int len) {
    if (len == 0) return 0;
    int *dp = (int*)malloc(len * sizeof(int));
    for (int i = 0; i < len; i++) dp[i] = 1;
    int maxSubLen = 1;
    for (int i = 1; i < len; i++) {
        for (int k = 0; k < i; k++) {
            if (nums[i] > nums[k]) {
                dp[i] = max(dp[i], dp[k] + 1);
                if (dp[i] >= maxSubLen) {
                    maxSubLen = dp[i];
                }
            }
        }
    }
    return maxSubLen;
}