最大子序和问题

所谓最大子序和问题，就是从给定的整数序列中找到连续的一串整数（至少包含 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 ] 为例，贪心算法查找最大子序和的思路是：从头遍历整个序列，对于每一个元素，如果它的存在有助于找到最大自序和，就把它加入到整形串中；反之则放弃当前元素，继续从下一个元素开始查找最大自序和。

可以看到，遍历过程中找到了很多个整数串，它们都是不同场景下查找最大子序和的最优解，其中最大的和是 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 语言程序：

1. #include <stdio.h>
2. #include <limits.h>
3. 
   
4. int maxSubArray(int* nums, int numsSize) {
5. int n = numsSize;      // 获取 nums 序列的元素个数
6. int maxSum = INT_MIN;   // 记录最大的子序和，初始值为最小的整数
7. int curSum = 0;         // 记录当前的子序和，初始值为0
8. 
   
9. // 遍历整个数组
10. for (int i = 0; i < n; ++i) {
11.        curSum += nums[i];  // 将当前元素加入当前子序列
12. 
    
13. // 若当前子序和大于之前的最大结果，更新最大子序和
14.        maxSum = curSum > maxSum ? curSum : maxSum;
15. 
    
16. // 若当前子序和为负，对结果无益，从 nums[i+1] 开始重新查找
17.        curSum = curSum > 0 ? curSum : 0;
18. }
19. 
    
20. return maxSum;  // 返回最终结果
21. }
22. int main() {
23. int nums[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
24. int numsSize = sizeof(nums) / sizeof(int);
25. int result = maxSubArray(nums, numsSize);
26. printf("最大子序和是 %d\n", result);
27. return 0;
28. }

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

纯文本复制

1. public class MaxSubArray {
2. public static int maxSubArray(int[] nums) {
3. int n = nums.length;      // 获取 nums 序列的元素个数
4. int maxSum = Integer.MIN_VALUE;   // 记录最大的子序和，初始值为最小的整数
5. int curSum = 0;         // 记录当前的子序和，初始值为0
6. 
   
7. // 遍历整个数组
8. for (int i = 0; i < n; ++i) {
9.            curSum += nums[i];  // 将当前元素加入当前子序列
10. 
    
11. // 若当前子序和大于之前的最大结果，更新最大子序和
12.            maxSum = Math.max(curSum, maxSum);
13. 
    
14. // 若当前子序和为负，对结果无益，从 nums[i+1] 开始重新查找
15.            curSum = Math.max(curSum, 0);
16. }
17. 
    
18. return maxSum;  // 返回最终结果
19. }
20. 
    
21. public static void main(String[] args) {
22. int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
23. int result = maxSubArray(nums);
24.        System.out.println("最大子序和是 " + result);
25. }
26. }