# d784. 一、連續元素的和
###### tags: `dp` `區間最大值`
##### link: https://zerojudge.tw/ShowProblem?problemid=d784
##### 類題: https://leetcode.com/problems/maximum-subarray/description/

* 不斷判斷當下的數字做為起點比較大，還是當下的數字加上之前的總和比較大。換句話說，所謂「狀態」指的是當下陣列的數字，而我們尋訪一次陣列來決定「是否選擇這個數字」
* dp 開 n 的大小即可，畢竟是子陣列的最大區間和，不會超過原始陣列範圍
* 最後，輸出最大值的時候要尋訪一次整個 dp 陣列

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n,k;
    cin>>n;
    while (n--){
        cin>>k;
        vector<int> table(k);
        vector<int> dp(k+1);
        for (int i=0;i<k;i++){
            cin>>table[i];
        }
        dp[0]=0;
        for (int i=0;i<k;i++){
            dp[i]=max(table[i],table[i]+dp[i-1]);
        }
        int res=-1e09;
        for (int i=1;i<k;i++){
            res=max(res,dp[i]);
        }
        cout<<res<<"\n";
    }

    return 0;
}