算法题--求最大和子序列

image.png

0. 链接

题目链接

1. 题目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

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

Follow up:

• If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

2. 思路1：单次遍历

1. 分析:

多个元素求和，正数会带来和的增加，负数会带来和的减少, 面临的任务是找到最佳的分组, 所以过程中需要及时剔除掉不好的分组;

分组的形式可以为

• 单个元素
• 多个元素

剔除的依据，就是当前分组是否可以超越历史最佳分组

2. 过程

(1) 设置变量

• max_sum: 表示历史最佳分组和
• curr_sum: 表示当前正在考察的分组的和

(2) 遍历查找

• 从左到右遍历
• 对每个位置的值,试图将该值累加到正在考察的分组的和curr_sum上，然后看它是否大于当前单个元素值，如果大于等于，说明当前分组仍有潜力；如果小于，说明当前分组没潜力，需要重新以当前元素值作为新的分组的起点
• 检查curr_sum是否超越了历史最佳分组和max_sum
• 最后得到历史最佳分组和max_sum并返回

3. 代码

# coding:utf8
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_sum = None
        max_sum = None
        for num in nums:
            if curr_sum is not None and max_sum is not None:
                curr_sum = max(curr_sum + num, num)
                max_sum = max(curr_sum, max_sum)
            else:
                max_sum = curr_sum = num

        return max_sum


solution = Solution()
print(solution.maxSubArray([0]))
print(solution.maxSubArray([-2, -1]))
print(solution.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

输出结果

0
-1
6

4. 结果

image.png