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

BM71 最长上升子序列(一)描述给定一个长度为 n 的数组 arr求它的最长严格上升子序列的长度。所谓子序列指一个数组删掉一些数也可以不删之后形成的新数组。例如 [1,5,3,7,3] 数组其子序列有[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。我们定义一个序列是严格上升的当且仅当该序列不存在两个下标 i 和 j 满足 ij且 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。求所有子数组的和的最大值。数据范围:1n2×105−100a[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)