最长的子阵列,其元素按顺序递增？

Question

给定数组= {1 2 3 3 2 4 6 7}

增长最长的子阵列是2 4 6 7.注意,这与最长的增加子序列不同,因为值必须是连续的.

这个问题有没有O(n)解决方案？

Answer 1

您可以使用动态编程.

伪代码:

def DP(a[]):
    dp[1] = 1
    for i = 2 to n:
        if a[i] > a[i - 1]:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = 1