53_最大子序和

类型：数组

最大子序和 💚 ⭐

https://leetcode-cn.com/problems/maximum-subarray/

❓ 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

💡 动态规划

我们考虑以下标 i 元素为结尾的子数组。那么 nums[i] 有两种选择：加入之前的数组，以及独立开始一个新数组。我们选择其中较大的。

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

由于在 dp 数组中 dp[i] 只与 dp[i - 1] 有关，因此我们可以只存储前一个 dp 值，使空间复杂度降低为 O(1).

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        pre = 0
        maxVal = nums[0]
        for val in nums:
            pre = max(pre + val, val)
            maxVal = max(maxVal, pre)
        return maxVal

时间复杂度：O(n)，空间复杂度：O(1)

💡 分治

对于一个区间 [l, r]，我们取 m = (l + r) // 2，对 [l, m] 和 [m + 1, r] 分治求解。当递归逐层深入到区间长度缩小为 1 的时候，递归开始回升。

对于一个区间 [l, r]，我们维护以下四个量：

lSum 表示 [l, r] 内以 l 为左端点的最大子段和
rSum 表示 [l, r] 内以 r 为右端点的最大子段和
mSum 表示 [l, r] 内的最大子段和
iSum 表示 [l, r] 的区间和

class Status:
    def __init__(self, lLen = 0, rLen = 0, mLen = 0, isCI = False, leftVal = 0, rightVal = 0):
        self.lLen = lLen # 左部连续递增长度
        self.rLen = rLen # 右部连续递增长度
        self.mLen = mLen # 中部连续递增长度
        self.isCI = isCI # 全区间是否连续递增
        self.leftVal = leftVal # 左端值
        self.rightVal = rightVal # 右端值

class Solution:
    def pushUp(self, lSub: Status, rSub: Status) -> Status:
        lLen = lSub.lLen + rSub.lLen if lSub.isCI and lSub.rightVal < rSub.leftVal else lSub.lLen
        rLen = rSub.rLen + lSub.rLen if rSub.isCI and lSub.rightVal < rSub.leftVal else rSub.rLen
        mLen = max(lLen, rLen, lSub.mLen, rSub.mLen, (lSub.rLen + rSub.lLen) if lSub.rightVal < rSub.leftVal else 0)
        isCI = True if lSub.isCI and rSub.isCI and lSub.rightVal < rSub.leftVal else False
        leftVal = lSub.leftVal
        rightVal = rSub.rightVal
        return Status(lLen, rLen, mLen, isCI, leftVal, rightVal)

    def get(self, nums: list, left: int, right: int) -> list:
        if left == right:
            return Status(1, 1, 1, True, nums[left], nums[right])
        mid = (left + right) // 2
        lSub = self.get(nums, left, mid)
        rSub = self.get(nums, mid + 1, right)
        return self.pushUp(lSub, rSub)

    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        return self.get(nums, 0, len(nums) - 1).mLen 