0.5 普通数组

[53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [0] * n
        dp[0] = nums[0]
        # dp[i] 表示以 nums[i] 结尾的子数组的最大和。
        for i in range(1,n):
            dp[i] = max(dp[i-1], 0) + nums[i]
        return max(dp)
```
[56. 合并区间](https://leetcode.cn/problems/merge-intervals/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        n = len(intervals)
        if n == 0:
            return []
        res = [intervals[0]]
        for i in range(1, n):
            if res[-1][1] >= intervals[i][1]:
                continue
            elif intervals[i][0] <= res[-1][1]:
                res[-1][1] = intervals[i][1]
            else:
                res.append(intervals[i])
        return res
```
[189. 轮转数组](https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[n-k:] + nums[:n-k]
```
[238. 除自身以外数组的乘积](https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [1] * n
        for i in range(1, n):
            res[i] = res[i - 1] * nums[i - 1]
        temp = 1
        for i in range(n - 2, -1, -1):
            temp *= nums[i + 1]
            res[i] = res[i] * temp
        return res

#   1 2 3 4
# 1 -
# 2   -
# 3     -
# 4       -
```
[41. 缺失的第一个正数](https://leetcode.cn/problems/first-missing-positive/?envType=study-plan-v2&envId=top-100-liked)
```python
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        st = set(nums)
        n = 1
        while n in st:
            n += 1
        return n
```
```python
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n + 1
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num - 1] = -abs(nums[num - 1])
        for i in range(n):
            if nums[i] > 0:
                return i + 1
        return n + 1
```