題目

輸入一個整型數(shù)組，數(shù)組里有正數(shù)也有負數(shù)。 數(shù)組中連續(xù)的一個或多個整數(shù)組成一個子數(shù)組，每個子數(shù)組都有一個和。 求所有子數(shù)組的和的最大值。要求時間復雜度為O(n)。 例如輸入的數(shù)組為1, -2, 3, 10, -4, 7, 2, -5，和最大的子數(shù)組為3, 10, -4, 7, 2，

代碼

#include<iostream>
using namespace std;

#define NUM 8

int main()
{
    int ary[NUM] = { 1, -2, 3, 10, -4, 7, 2, -5 };
    
    int max = 0;//保存最大和
    int curSum = 0;//保存當前和
    int curStart = 0;//當前和的起始位置
    int start = 0;//最大和的起始位置
    int end = 0;//最大和的終止位置
    for (int i = 0; i<NUM; i++)
    {
        if (i == 0)
        {
            curSum = max = ary[i];
            continue;
        }

        if (curSum<0)
        {
            curSum = 0;//與負數(shù)相加，和會減小，所以拋棄以前的和
            curStart = i;
        }
        //最大值已經被保存下來，所以請大膽的繼續(xù)往前加
        curSum += ary[i];
        //當前和被保存為最大值，記錄下它的起始位置和結束位置
        if (curSum>max)
        {
            max = curSum;
            start = curStart;
            end = i;
        }
    }

    cout << "和最大的子數(shù)組為：" << endl;
    for (int i = start; i <= end; i++)
    {
        cout << ary[i] << " ";
    }
    cout << "= " << max;
    cin.get();
    return 0;
}

結果

結果.png