求解最大升序子序列问题(动态规划)

最大升序子序列：给定数组 [1,7,3,5,9,4,8]，则该数组的最大升序子序列为 1,3,5,9，不要求连续。

dp[i]存储第i个位置时，最大升序子序列的长度。

状态转移方程：dp[i] = dp[j] + 1 ， dp[j] = max(dp[0,i-1])

初始状态dp[i]=1

求解最大升序子序列长度不像是正规的动态规划问题，每次求解dp[i] 都需要遍历索引 i 之前的数组元素。

具体的，如何求解以 i 结尾的数组的最大升序子序列长度。

遍历arr[ 0 : i ] 内部的数组

若存在元素满足arr[j]<arr[i] 且 lis[j]+1 > lis[i] ,

then lis[i] = list[j] +1

def LIS(arr):
    if not arr or len(arr)==1:
        return 1
    dp = [0 for _ in range(len(arr))]
    for i in range(len(arr)):
        dp[i] = 1
        for j in range(i):
            if arr[j] < arr[i] and dp[j]+1>dp[i]:
                dp[i] = dp[j]+1
    return dp[-1]

贪心算法+二分优化复杂度O(nlog2n)

对于nlog2n的解法，此时的数组dp[i]的含义为以i结尾的最大升序子序列，注意此时的dp是动态更新的。当遍历到数组元素arr[i]时，若arr[i]小于dp[i]，则在dp中寻找到arr[i]存放的位置并覆盖。注意到覆盖掉dp中原来的元素并不影响此时dp的长度，即之前找到的最大升序子序列长度依然是dp的长度。但为什么要覆盖掉呢？因为只有覆盖掉那个较大的元素，当后面还有更小且更长的升序序列时，这些序列才会被加到dp当中。（不知道说清楚了没有，没看懂的话直接看例子吧）

找一个容易理解的例子：arr 1 3 2 4 5 2 2 2 。它的最大升序子序列为 1 2 2 2 2

此时的dp数组存储过程，遍历arr

dp:　　1

dp:　　1　　3　　　　　(arr[1]比dp中最后一个元素1大，直接追加)

dp:　　1　　2 　　　　(arr[2]比dp中最后一个元素3小，通过二分法找到arr[2]的位置并覆盖)

dp:　　1　　2　　4

dp:　　1　　2　　4　　5

dp:　　1　　2　　2　　5　　(arr[5]比dp中最后一个元素5小，找到dp中arr[5]的位置并覆盖)

dp:　　1　　2　　2　　2

dp:　　1　　2　　2　　2　　2

 1  def LIS(self,arr):
 2      n = len(arr)
 3      dp = [arr[0]]
 4      for i in range(1,n):
 5          if arr[i]>=dp[-1]:
 6              dp.append(arr[i])
 7          else:
 8              l,r = 0,len(dp)-1
 9              while l<r:
10                  mid = (l+r)//2
11                  if dp[mid]>arr[i]:
12                      r = mid-1
13                  else:
14                      l = mid+1
15              dp[l] = arr[i]
16      return len(dp)

附上代码 python