連續子數組的最大和—牛客網（C++實作）

一、題目描述

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。給一個數組，傳回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)

二、程式設計思路

要求連續子數組的最大和，可以通過周遊每個元素及其後續元素之和sum，将sum儲存到vector容器SUM中。最後求SUN中的最大值，即為連續子數組的最大和。以數組{6,-3,-2,7,-15,1,2,2}為例，過程如下：

索引值i=0時：{6}，{6,-3}，{6,-3,-2}，{6,-3,-2,7}，{6,-3,-2,7,-15}，{6,-3,-2,7,-15,1}，{6,-3,-2,7,-15,1,2}，{6,-3,-2,7,-15,1,2,2}；

索引值i=1時：{-3}，{-3,-2}，{-3,-2,7}，{-3,-2,7,-15}，{-3,-2,7,-15,1}，{-3,-2,7,-15,1,2}，{-3,-2,7,-15,1,2,2}；

索引值i=2時：{-2}，{-2,7}，{-2,7,-15}，{-2,7,-15,1}，{-2,7,-15,1,2}，{-2,7,-15,1,2,2}；

索引值i=3時：{7}，{7,-15}，{7,-15,1}，{7,-15,1,2}，{7,-15,1,2,2}；

索引值i=4時：{-15}，{-15,1}，{-15,1,2}，{-15,1,2,2}；

索引值i=5時：{1}，{1,2},{1,2,2}；

索引值i=6時：{2},{2,2}；

索引值i=7時：{2}。

分别計算以上各個數組的和sum，将其儲存到SUM容器中，最後利用函數max_element()求得SUM中最大值，即為連續子數組的最大和。注意：使用max_element()函數需要如下頭檔案。

#include <algorithm>
           

三、程式

int FindGreatestSumOfSubArray(vector<int> array) 
    {
    vector<int>SUM;
    for(int i=0;i<array.size();i++)
    {
        SUM.push_back(array[i]);
    }
    for(int i=0;i<array.size()-1;i++)
    {
        int sum=array[i];
        for(int j=i+1;j<array.size();j++)
        {
            sum+=array[j];
            SUM.push_back(sum);
        }
    }
    vector<int>::iterator max=max_element(SUM.begin(),SUM.end());
    return *max;
    }
           

四、運作效果圖