30805：严格最长递增子序列长度

题目

求整数序列的严格最长递增子序列长度，保持原顺序且不允许相等元素连续递增。

解析

令 dp[i] 表示以第 i 个元素结尾的最长严格递增子序列长度。枚举所有 j < i，只有 items[j] < items[i] 时才能从 dp[j] 转移。所有辅助存储完成后才设置输出。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool lis_length_i64(
    const int64_t *items,
    size_t count,
    size_t *out_length
) {
    if (out_length == NULL || (count > 0 && items == NULL)) {
        return false;
    }
    if (count == 0) {
        *out_length = 0;
        return true;
    }
    if (count > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *dp = malloc(count * sizeof *dp);
    if (dp == NULL) {
        return false;
    }
    size_t best = 0;
    for (size_t i = 0; i < count; ++i) {
        dp[i] = 1;
        for (size_t j = 0; j < i; ++j) {
            if (items[j] < items[i] &&
                dp[j] < SIZE_MAX && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > best) {
            best = dp[i];
        }
    }
    free(dp);
    *out_length = best;
    return true;
}

双重循环访问每一对下标，时间复杂度为 $O(n^2)$，状态数组占用 $O(n)$ 空间。