題目

輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)涕癣。數(shù)組中一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組哗蜈。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度為O(n)

例如：輸入數(shù)組為{1坠韩，-2距潘，3，10只搁，-4音比，7，2氢惋，-5 }洞翩，和最大的子數(shù)組為{3，10焰望，-4骚亿，7，2}熊赖，因此輸出為該子數(shù)組的和為18

分析

從頭到尾累加數(shù)組中的每個(gè)數(shù)字來分析規(guī)律

• 初始化和為0
• 第一步加上第一個(gè)數(shù)字1循未，此時(shí)和為1
• 第二步加上數(shù)字-2，和為-1
• 第三步加上數(shù)字3，這里注意：之前累加和為-1的妖，小于0绣檬，如果用-1加上3，得到和為2嫂粟，比3本身還小娇未。也就是說，從第一個(gè)數(shù)字開始的子數(shù)組和小于從第三個(gè)數(shù)字開始的子數(shù)組的和星虹。因此零抬，可以不用考慮從第一個(gè)數(shù)字開始的子數(shù)組，之前的累加的和被拋棄
• 現(xiàn)在從第3個(gè)數(shù)字重新開始累加宽涌，此時(shí)和為3
• 第四步加10平夜，得到和13
• 第五步加上-4，得到和為9卸亮。可以看到結(jié)果比之前的和要小忽妒，因此把之前得到的和13保存下來，因?yàn)樗锌赡苁亲畲蟮淖訑?shù)組的和
• 第六步加上數(shù)字7兼贸，結(jié)果為16段直，此時(shí)和比之前最大的和13大，所以更新子數(shù)組的最大和
• 第七步加上2溶诞，累加得到和為18鸯檬，同時(shí)更新最大子數(shù)組和
• 第八步加上最大一個(gè)數(shù)字-5，由于得到的和13小于之前的18螺垢。因此最大的子數(shù)組和為18

總結(jié)

在每次元素累加和小于0時(shí)喧务，從下一個(gè)元素重新開始累加。否則直接累加枉圃，更新最大值功茴。

算法實(shí)現(xiàn)

#include <iostream>

bool invalidInput = false; // 無效輸入

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

    int currentSum = 0; // 當(dāng)前求和值
    int greatestSum = 0x80000000; // 最大求和值
    for (int i = 0; i < length; i++) {
        if (currentSum <= 0) { // 當(dāng)前求和結(jié)果值小于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;
}

暴力求解

如果不要求時(shí)間復(fù)雜度為O(n)，很容易想到的就是雙重遍歷求和讯蒲，時(shí)間復(fù)雜度為O(n²)

先找出從第1個(gè)元素開始的最大子數(shù)組痊土，而后再從第2個(gè)元素開始找出從第2個(gè)元素開始的最大子數(shù)組，依次類推墨林，比較得出最大的子數(shù)組赁酝。

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》