剑指offer - 连续子数组的最大和

题目

输入一个整型数组，数组里有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

例如：输入数组为{1，-2，3，10，-4，7，2，-5 }，和最大的子数组为{3，10，-4，7，2}，因此输出为该子数组的和为18

分析

从头到尾累加数组中的每个数字来分析规律

• 初始化和为0
• 第一步加上第一个数字1，此时和为1
• 第二步加上数字-2，和为-1
• 第三步加上数字3，这里注意：之前累加和为-1，小于0，如果用-1加上3，得到和为2，比3本身还小。也就是说，从第一个数字开始的子数组和小于从第三个数字开始的子数组的和。因此，可以不用考虑从第一个数字开始的子数组，之前的累加的和被抛弃
• 现在从第3个数字重新开始累加，此时和为3
• 第四步加10，得到和13
• 第五步加上-4，得到和为9。可以看到结果比之前的和要小，因此把之前得到的和13保存下来，因为它有可能是最大的子数组的和
• 第六步加上数字7，结果为16，此时和比之前最大的和13大，所以更新子数组的最大和
• 第七步加上2，累加得到和为18，同时更新最大子数组和
• 第八步加上最大一个数字-5，由于得到的和13小于之前的18。因此最大的子数组和为18

总结

在每次元素累加和小于0时，从下一个元素重新开始累加。否则直接累加，更新最大值。

算法实现

#include <iostream>

bool invalidInput = false; // 无效输入

int findGreatestSumOfSubArray(int *pData, int length) {
    if ((pData == nullptr) || (length <= 0)) {
        invalidInput = true;
        return 0;
    }

    int currentSum = 0; // 当前求和值
    int greatestSum = 0x80000000; // 最大求和值
    for (int i = 0; i < length; i++) {
        if (currentSum <= 0) { // 当前求和结果值小于0 
            currentSum = pData[i];
        } else {
            currentSum += pData[i]; // 累加
        }
        
        if (currentSum > greatestSum) { // 更新最大值 
            greatestSum = currentSum;
        }
    }

    return greatestSum;
}

void Test(char* testName, int* pData, int nLength, int expected, bool expectedFlag) {
    if(testName != nullptr)
        printf("%s begins: \n", testName);

    int result = findGreatestSumOfSubArray(pData, nLength);
    if(result == expected && expectedFlag == invalidInput)
        printf("Passed.\n");
    else
        printf("Failed.\n");
}

void Test1() {
    int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
    Test("Test1", data, sizeof(data) / sizeof(int), 18, false);
}

void Test2() {
    int data[] = {-2, -8, -1, -5, -9};
    Test("Test2", data, sizeof(data) / sizeof(int), -1, false);
}

void Test3() {
    int data[] = {2, 8, 1, 5, 9};
    Test("Test3", data, sizeof(data) / sizeof(int), 25, false);
}

void Test4() {
    Test("Test4", nullptr, 0, 0, true);
}

int main(int argc, char* argv[]) {
    Test1();
    Test2();
    Test3();
    Test4();

    return 0;
}

暴力求解

如果不要求时间复杂度为O(n)，很容易想到的就是双重遍历求和，时间复杂度为O(n²)

先找出从第1个元素开始的最大子数组，而后再从第2个元素开始找出从第2个元素开始的最大子数组，依次类推，比较得出最大的子数组。

nt maxSubArray(int *array, int length) {
    int maxSum = 0x80000000;

    if ((array == nullptr) || (length <= 0)) {
        return 0;
    }

    for (int i = 0; i < length; i++)
    {
        int currentSum = 0;
        for (int j = i; j < length; j++)
        {
            currentSum += array[j];
            if (currentSum > maxSum)
            maxSum = currentSum;   
        }
    }
    return maxSum;
}

参考

《剑指offer》