求子数组的最大和

题目

输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 输入 数组为1, -2, 3, 10, -4, 7, 2, -5。最大的子数组为3, 10, -4, 7, 2 输出 最大子数组的和18。

理解

赌徒连续多日赌博，每日或赢或输，赢钱用正数表示，输钱负数表示 计算该赌徒最有钱的时候，有多少钱？

误区

只取连续的正数之和！

解法示例

1. 暴力破解法

//最大子数组之和
int max_value(int a[], int size) {
	if (size <= 0) {
		std::cout << "error array size";
		return -1;
	}//防御编程

	int sum = 0;
	int max = -(1 << 31);//位运算高效
	int cur = 0;

	while (cur < size) {    //1, -2, 3, 10, -4, 7, 2, -5
		sum += a[cur++];
		if (sum > max) {
			max = sum;
		}
		else if (sum < 0) {
			sum = 0;
		}
	}//循环结束
	return max;
}

int max_value_test(void) {
	int data[] = { 1, -2, 3, 10, -4, 7, 2, -5 };
	int ret;

	ret = max_value(data, sizeof(data) / sizeof(data[0]));

	std::cout << "max = " << ret << std::endl;
	system("pause");
	return 0;
}

int main()
{
	max_value_test();
	return 0;
}

运行结果为

max = 18

2. 分而治之法

/*
 * @Author: 不懂算法的小白
 * @Date: 2022-10-15 16:22:18
 * @Last Modified by: 不懂算法的小白
 * @Last Modified time: 2022-10-15 17:32:47
 */

#include <iostream>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <limits.h>

int target[2] = {0, 0}; //记录左右节点。
enum Pos
{
    LEFT = 0,
    RIGHT = 1
};

int max(int arg_len, ...)
{
    int max = INT_MIN;
    va_list v_list;
    va_start(v_list, arg_len);
    for (int i = 0; i < arg_len; i++)
    {
        int a = va_arg(v_list, int);
        if (a > max)
        {
            max = a;
        }
    }
    return max;
}

int CrossingSubArray(int x[], int low, int mid, int high)
{
    if (low == high)
    {
        return x[low];
    }
    
    /*左子数组最大值*/
    int s_left = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; i--)
    {
        sum += x[i];
        if (sum > s_left)
        {
            s_left = sum;
            target[LEFT] = i;
        }
    }//注意顺序，从右往左
    
    /*右子数组最大值*/
    int s_right = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= high; i++)
    {
        sum += x[i];
        if (sum > s_right)
        {
            s_right = sum;
            target[RIGHT] = i;
        }
    }//从左往右
    
    return s_right + s_left;
}

int MaxSubArray(int x[], int low, int high)
{
    if (low == high)
    {
        return x[low];
    }
    else
    {
        int mid = (low + high) / 2;
        int s1 = MaxSubArray(x, low, mid);
        int s2 = MaxSubArray(x, mid + 1, high);
        int s3 = CrossingSubArray(x, low, mid, high);
        return max(3, s1, s2, s3);
    }
}

int main()
{
	int a[8] = {1, -2, 3, 10, -4, 7, 2, -5};

    int sum = MaxSubArray(a, 0, 7);
    printf("最大子数组和为%d,在%d和%d之间\n", sum, target[LEFT], target[RIGHT]);
    return 0;
}

运行结果为

最大子数组和为18,在2和6之间

3. 动态规划法

#include "global.h"

int maxSubArray(int a[], int n)
{
    int *rec = new int[n];
    int *d = new int[n];
    memcpy(d, a, sizeof(int) * n);//复制a数组
    rec[n-1] = n;//设置最后一个结束

    for (int i = n - 2; i >= 0; i--)
    {
        if (d[i + 1] > 0)
        {
            d[i] = a[i] + d[i + 1];
            rec[i] = rec[i + 1];
        }//上一个数组大于0
        else
        {
            d[i] = a[i];
            rec[i] = i;
        }
    }//从倒数第二个开始遍历

    int max = d[0];
    int l;
    int r;
    for (int i = 1; i < n; i++)
    {
        if (d[i] > max)
        {
            l = i;
        }
    }//找到最大的子数组的左边界
    max = d[l];
    r = rec[l];
    printf("max=%d, l=%d, r=%d\n", max, l, r);
    delete[] d;
    delete[] rec;
}

int main()
{
    int a[8] = {1, -2, 3, 10, -4, 7, 2, -5};
    int sum = maxSubArray(a, 8);
    return 0;
}