[筆記] 最大區間和

筆者在上上周六去參加 ITSA 桂冠

有一題一直 TLE (無奈

於是在上周末想了一整天

終於想出個解法

題目呢...我忘了XDD

只記得是種蘋果樹，每個蘋果樹有它的價值，只能連續取，也可從中間開始取

求最大利潤為？( 如果全部賠本，就可以全不取

為最大區間和問題

INPUT:
　　每行第一個數 m 代表有 m 棵蘋果樹，接下來有 m 個 數字，代表蘋果樹的利潤

OUTPUT:
　　最大利潤


首先，來個暴力解

應該看得懂，就不加註解了(懶

#include < iostream >
using namespace std;
int main()
{
    int m;
    while( cin >> m )
    {
        int ls[m], max = 0;
        for( int i = 0; i < m; i++ )
            cin >> ls[i];
        for( int i = 0; i < m; i++ )
            for( int j = i; j < m; j++ )
            {
                int sum = 0;
                for( int k = i; k <= j; k++ )
                    sum += ls[k];
                if( max < sum )
                    max = sum;
            }
        cout << max << endl;
    }
    return 0;
}

時間複雜度為 O(n^3)
空間複雜度為 O(n)


再來是，進階版

效率較好的窮舉

把每一個數讀入時，

就加前項的總和，成為下一個總和

ex:
　s[0] = ls[0]
　s[1] = s[0] + ls[1]
　s[2] = s[1] + ls[2]
　......

再來從第一項開始扣

把每一項 s[] 的 ls[] 依序扣掉


圖解

#include < iostream >
using namespace std;
int main()
{
    int m;
    while( cin >> m )
    {
        int ls[m],s[m], input, max = 0;

        // 先讀入第一項
        cin >> ls[0];
        s[0] = ls[0];
        for( int i = 1; i < m; i++ )
        {
            // 依序讀入 2-m 項
            cin >> input;
            ls[i] = input;

            // 此項和 = 前一項的和 + 輸入值
            s[i] = s[i-1] + input;
            if( max < s[i] )
                max = s[i];
        }
        for( int i = 0; i < m; i++ )
            for( int j = 0; j < m; j++ )
            {
                // 依序從 s[] 扣掉 ls[i]
                s[j] -= ls[i];
                if( max < s[j] )
                    max = s[j];
            }
        cout << max << endl;
    }
    return 0;
}

時間複雜度為 O(n^2)
空間複雜度為 O(n)


最後，其實很簡單

沒有想到罷了( 慚愧!!

假設區間和為 SUM;

只要區間和是正的，那後面就有可能有一個數，使區間和更大

如果區間和是負的，那後面就絕對不可能有一個數 X ，使得 SUM + X > X;

所以只要該段區間和為負，區間和就重置從 0 開始

#include < iostream >
using namespace std;
int main()
{
    int m;
    while( cin >> m )
    {
        int input, sum = 0, max = 0;
        for( int i = 0; i < m; i++ )
        {
            cin >> input;
            sum += input;
            if( sum < 0 )
                sum = input;
            if( max < sum )
                max = sum;
        }
        cout << max << endl;
    }
    return 0;
}

時間複雜度為 O(n)
空間複雜度為 O(1)