经典题目（5）：最长上升子序列,连续子数组的最大和

BM71 最长上升子序列(一)

描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是严格上升的，当且仅当该序列不存在两个下标 i 和 j 满足 i<j且 arri≥arrj

数据范围： 0≤n≤1000

要求：时间复杂度 O(n2)， 空间复杂度 O(n)

代码

class Solution: def LIS(self , arr: List[int]) -> int: # write code here if len(arr)==0: return 0 dp=[1]*len(arr) for right in range(1,len(dp)): for left in range(right): if arr[left]<arr[right]: dp[right]=max(dp[right],dp[left]+1) return max(dp)

BM72 连续子数组的最大和

描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

数据范围:

1<=n<=2×105

−100<=a[i]<=100

要求:时间复杂度为 O(n)，空间复杂度为 O(n)

进阶:时间复杂度为 O(n)，空间复杂度为 O(1)

代码

class Solution: def FindGreatestSumOfSubArray(self , array: List[int]) -> int: # write code here dp=[0]*len(array) if len(array)==1: return array[0] dp[0]=array[0] for i in range(1,len(array)): dp[i]=max(dp[i-1]+array[i],array[i]) return max(dp)