数组一直都是比较长考的考点。
难度中等2683
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3] 输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7] 输出：1
思考：判断一个数组的最长递增子序列，本来想是用回溯，结束条件是遍历到最后一位数，提取出一个栈，栈中数满足递增子序列的方法。
但是，好像有点麻烦，主要是没写出来。
但是动态规划就很好想。首先1.开一个多大长度的dp，这里是一维数组，只需要长度为n的dp就好。
dp = [1] * len(nums)
如何初始化条件。，初始化为1，为什么， 因为当前数值都可以作为递增数的起始位置，所以为1。
如何去遍历，这里i位置需要用前面的所有状态去判断，来判断最大的值是多少，所以，用两个指针进行判断。
- Max = 0
- for i in range(len(nums)):
- for j in range(i):
- if nums[j] < nums[i]: # 当发现前面有数小于当前数，也就是可以作为递增的条件
- dp[i] = max(dp[j]+1,dp[i]) # 一直不断选择
- # 动态更新
- Max = max(dp[i],Max)
- return Max
但是时间复杂度好像大了一点，可能因为每一次都在判断，动态判断在运行二维数组的时候比较好用，这里可以直接判断dp数组。
- class Solution:
- def lengthOfLIS(self, nums: List[int]) -> int:
- n = len(nums)
- dp = [1] * n
- for i in range(n):
- for j in range(i):
- if nums[j] < nums[i]:
- dp[i] = max(dp[i],dp[j]+1)
- return max(dp)
难度中等5197
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
思考。这道题也是用动态规划做，那就是几个步骤
1.dp用多大的，还是n的数组
2.初始化怎么做：这里初始化为0就行，因为判断不用加上初始化的值。还有，第一个数值需要初始化为0，或者开个n+1 大小的数组。
3，状态函数怎么判断。用一个指针遍历所有数组，连续数组和，那意味着只需要判断前一个dp对当前的影响即可。这里求得最大值，所有只要前面对当前的影响是正影响，就加上，是负影响就去除。
- dp = [0] * n
- for i in range(1,n):
- if dp[i-1] + nums[i] > nums[i]:
- dp[i] = dp[i-1] + nums[i]
- else:
- dp[i] = nums[i]
- return max(dp)