本文共 3641 字，大约阅读时间需要 12 分钟。

题目描述

最大连续子序列和。（至少包含一个数组）

例子

Input: [-2,1,-3,4,-1,2,1,-5,4],

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

思想

法1 - DP。dp[i]表示以i位置结尾的最大值，dp[i] = max(dp[i-1] + nums[i], nums[i])； 法2 - 贪心。如果之前的和小于0，则从当前数字开始。即如果summ<0，则将summ置0；否则继续summ + num。 法3 - 分治法。 考虑区间[l, r]内的答案如何计算？ 令 mid = (l + r) / 2，则该区间的答案是三部分取最大值，分别是： (a) 区间 [l, mid] 内的答案（递归）。 (b) 区间 [mid + 1, r] 内的答案（递归）。 (c) 跨越 mid和mid+1 的连续子序列。 其中，(c) 部分只需要从 mid 开始向 l 找连续的最大值，以及从 mid+1 开始向 r 找最大值即可，在线性时间内可以完成。 递归终止条件显然是 l==r ，此时直接返回 nums[l]。

每层时间复杂度是 O(n)，总共有 O(logn) 层，故总时间复杂度是 O(nlogn)。

解法1

可以优化空间复杂度，优化后类似法2

class Solution(object):    def maxSubArray(self, nums):        """        :type nums: List[int]        :rtype: int        """        res = nums[0]        dp = [0] * len(nums)    # dp[i]表示以i位置结尾的最大值        dp[0] = nums[0]        for i in range(1, len(nums)):            dp[i] = max(dp[i-1] + nums[i], nums[i])            res = max(res, dp[i])        return res

解法2

class Solution(object):    def maxSubArray(self, nums):        """        :type nums: List[int]        :rtype: int        """        res = summ = nums[0]        for num in nums[1:]:            if summ < 0:                summ = 0            summ += num            res = max(res, summ)        return res

解法3

class Solution(object):    def maxSubArray(self, nums):        """        :type nums: List[int]        :rtype: int        """        return self.helper(0, len(nums)-1, nums)        def helper(self, left, right, nums):        if left == right:            return nums[left]                mid = (left + right) >> 1        # The maxSum including mid and mid+1        lmax = nums[mid]        rmax = nums[mid+1]        lsum = rsum = 0        for i in range(mid, left-1, -1):            lsum += nums[i]**加粗样式**            lmax = max(lsum, lmax)        for i in range(mid+1, right+1):            rsum += nums[i]            rmax = max(rsum, rmax)                    return max(max(self.helper(left, mid, nums), self.helper(mid+1, right, nums)), lmax+rmax)

题目描述

给定无序整数数组，输出最长递增子序列长度。(不连续)

例子

Input: [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

思想

看到最大，最长 → 想到DP。 法1 - dp[i]表示以nums[i]结尾的最长递增子序列的长度； 初始状态：dp = [1] * len(nums)； 状态方程：dp[i] = max(dp[i], dp[j] + 1) if nums[j] < nums[i] 对于j=0,1…i-1； 时间复杂度O(n^2)。 法2 - 优化，时间复杂度(nlogn)

对于一个上升子序列，显然当前最后一个元素越小，越有利于添加新的元素，这样LIS长度自然更长。

维护一arr数组，数组元素表示长度为i+1的LIS结尾元素的最小值(保证每一位都是最小值)， 此时arr数组的长度就是LIS的长度

对于每一个num，如果≥arr[-1], 直接插入尾部；否则找到arr第一个大于num的位置, 替换

解法1

class Solution(object):    def lengthOfLIS(self, nums):        """        :type nums: List[int]        :rtype: int        """        if not nums:            return 0                dp = [1] * len(nums)    # dp[i]表示以i结尾的最长递增子序列的长度        for i in range(len(nums)):            for j in range(i):                if nums[j] < nums[i]:                    dp[i] = max(dp[i], dp[j] + 1)        return max(dp)

解法2

存储长为i+1的LIS结尾元素的最小值

class Solution(object):    def lengthOfLIS(self, nums):        """        :type nums: List[int]        :rtype: int        """        arr = []        for num in nums:            if not arr or num > arr[-1]:                arr.append(num)            else:                pos = self.getFirstLarger(arr, num)                arr[pos] = num        return len(arr)                    def getFirstLarger(self, arr, num):        l = 0        r = len(arr) - 1        while l <= r:            mid = (l + r) >> 1            if arr[mid] < num:                l = mid + 1            else:                if mid > 0 and arr[mid-1] > num:                    r = mid - 1                else:                    return mid

Ref

转载地址：http://tzkfb.baihongyu.com/