最大子序和问题（非常详细，附带源码）

所谓最大子序和问题，就是从给定的整数序列中找到连续的一串整数（至少包含 1 个整数），要求这串整数的和是所有整数串中最大的。

例如，[ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 是一个整数序列，其中和最大的整数串是 [ 4, -1, 2, 1 ]，所有整数的和是 6。

再例如，[ -1, 4, -2 ] 是一个整数序列，其中和最大的整数串是 [4]，只包含一个整数 4。

最大子序和问题可以用贪心算法解决，接下来就给大家讲解具体的实现思路。

贪心算法解决最大子序和问题

我们知道，贪心算法的核心是每次都选择当下最优的解决方案，又叫局部最优解。

以 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 为例，贪心算法查找最大子序和的思路是：从头遍历整个序列，对于每一个元素，如果它的存在有助于找到最大自序和，就把它加入到整形串中；反之则放弃当前元素，继续从下一个元素开始查找最大自序和。

元素	分析	是否选择	整数串
-2	-2 是负数，它的存在只会拉低后续元素的总和，不利于找到最大自序和	不选	[ ]
1	1 是正数，它可以进一步抬高后续元素的总和，有助于找到最大自序和	选	[1]，和为 1
-3	[1, -3] 的和是 -2，是负数，[1, -3] 的存在只会拉低后续元素的总和，不利于找到最大子序和	不选	[ ]
4	4 是正数，它可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4]，和为 4
-1	[4, -1] 的和是 3，是正数，[4, -1] 可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4, -1]，和为 3
2	[4, -1, 2] 的和是 5，是正数，[4, -1, 2] 可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4, -1, 2]，和为 5
1	[4, -1, 2, 1] 的和是 6，是正数，[4, -1, 2, 1] 可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4, -1, 2, 1]，和为 6
-5	[4, -1, 2, 1, -5] 的和是 1，是正数，[4, -1, 2, 1, -5] 可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4, -1, 2, 1, -5]，和为 1
4	[4, -1, 2, 1, -5，4] 的和是 5，是正数，[4, -1, 2, 1, -5，4] 可以进一步抬高后续元素的总和，有助于找到最大子序和	选	[4, -1, 2, 1, -5，4]，和为 5

可以看到，遍历过程中找到了很多个整数串，它们都是不同场景下查找最大子序和的最优解，其中最大的和是 6，它就是 [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ] 这个序列的最大子序和。

下面是贪心算法解决最大子序和问题的伪代码：

maxSubArray(nums):
    n <- length(nums) // 获取 nums 序列的元素个数
    maxSum <- MIN_INT // 记录最大的子序和，初始值为最小的整数
    curSum <- 0 // 记录当前的子序和，初始值为0
   
    // 遍历整个数组
    for i<-0 to n:
        curSum <- curSum + nums[i]
        // 若当前整数串的和大于之前的最大结果，对结果进行更新
        maxSum <- max(curSum, maxSum)
        // 若当前整数串的和为负，对结果无益，则从 nums[i+1]开始重新查找。
        curSum <- max(0, curSum)

    return maxSum

贪心算法实现最大子序和问题

下面是用贪心算法实现最大子序和问题的 C 语言程序：

#include <stdio.h>
#include <limits.h>

int maxSubArray(int* nums, int numsSize) {
    int n = numsSize;      // 获取 nums 序列的元素个数
    int maxSum = INT_MIN;   // 记录最大的子序和，初始值为最小的整数
    int curSum = 0;         // 记录当前的子序和，初始值为0

    // 遍历整个数组
    for (int i = 0; i < n; ++i) {
        curSum += nums[i];  // 将当前元素加入当前子序列

        // 若当前子序和大于之前的最大结果，更新最大子序和
        maxSum = curSum > maxSum ? curSum : maxSum;

        // 若当前子序和为负，对结果无益，从 nums[i+1] 开始重新查找
        curSum = curSum > 0 ? curSum : 0;
    }

    return maxSum;  // 返回最终结果
}
int main() {
    int nums[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    int numsSize = sizeof(nums) / sizeof(int);
    int result = maxSubArray(nums, numsSize);
    printf("最大子序和是 %d\n", result);
    return 0;
}

下面是用贪心算法实现最大子序和问题的 Java 程序：

public class MaxSubArray {
    public static int maxSubArray(int[] nums) {
        int n = nums.length;      // 获取 nums 序列的元素个数
        int maxSum = Integer.MIN_VALUE;   // 记录最大的子序和，初始值为最小的整数
        int curSum = 0;         // 记录当前的子序和，初始值为0

        // 遍历整个数组
        for (int i = 0; i < n; ++i) {
            curSum += nums[i];  // 将当前元素加入当前子序列

            // 若当前子序和大于之前的最大结果，更新最大子序和
            maxSum = Math.max(curSum, maxSum);

            // 若当前子序和为负，对结果无益，从 nums[i+1] 开始重新查找
            curSum = Math.max(curSum, 0);
        }

        return maxSum;  // 返回最终结果
    }

    public static void main(String[] args) {
        int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
        int result = maxSubArray(nums);
        System.out.println("最大子序和是 " + result);
    }
}

下面是用贪心算法实现最大子序和问题的 Python 程序：

def maxSubArray(nums):
    n = len(nums)      # 获取 nums 序列的元素个数
    maxSum = float('-inf')   # 记录最大的子序和，初始值为负无穷大
    curSum = 0          # 记录当前的子序和，初始值为0

    # 遍历整个数组
    for i in range(n):
        curSum += nums[i]  # 将当前元素加入当前子序列

        # 若当前子序和大于之前的最大结果，更新最大子序和
        maxSum = max(curSum, maxSum)

        # 若当前子序和为负，对结果无益，从 nums[i+1] 开始重新查找
        curSum = max(0, curSum)

    return maxSum  # 返回最终结果

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = maxSubArray(nums)
print("最大子序和是", result)

运行程序，执行结果为：

最大子序和是 6

最大子序和问题（非常详细，附带源码）

贪心算法解决最大子序和问题

贪心算法实现最大子序和问题

相关文章