ZeroJudge D784: 連續元素的和

已知 N 個元素的整數數列，找出該數列連續元素的和的最大值。

範例測資

範例輸入範例輸出
第一行的數字，代表有幾組測試資料，第二行開始的每一行即為一筆測試資料。
每一筆測試資料以空格分開數字：
第一個整數為數列長度 N，其範圍為 [1, 100] 的整數；
接下來的 N 個整數，其範圍為 [-10000, 10000] 的整數。		對每一筆測試資料，以一行輸出最大連續元素的和。
3
5 1 2 -3 4 5
5 1 2 3 4 5
6 10 -5 7 6 -1 -3		9
15
18

解題思路

使用 For迴圈 將資料收到一個 陣列/Vector 中。使用一個 For迴圈 來設定現在要加總的起點，裡面再放一個 For迴圈 從上一個For迴圈中的值跑到M結束，每次都將數列中的數字加到一個變數中，並且每次都進行最大值的比對。最後將最大值的變數輸出即可。

範例程式碼－ZeroJudge D784: 連續元素的和

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        int M;
        cin >> M;
        vector<int>num;
        for (int j = 0; j<M; j++)
        {
            int tmp;
            cin >> tmp;
            num.push_back(tmp);
        }
        int max = -999;
        for (int j = 0; j<M; j++)
        {
            int sum = 0;
            for (int k = j; k<M; k++)
            {
                sum += num[k];
                if (sum > max) max = sum;
            }
        }
        cout << max << endl;
    }
}

//ZeroJudge D784
//Dr. SeanXD
標籤

相關文章

發佈留言