PAT甲級1007 Maximum Subsequence Sum c++

Maximum Subsequence Sum

最大（連續）子區間和

題目大意：

 給定k個整數的序列

 找出最大連續子序列的區間和，并輸出區間第一個和最後一個數字

 若答案不唯一，選擇左端點最小的區間

 若答案仍不唯一，選擇右端點最小的區間

 若k個數字都是負數，則其最大和為定為0，并輸出序列第一個數字和最後一個數字

思路：

經典dp問題

 集合：用f[i]表示，右端點為i的區間的集合

 屬性：和的最大值max

 集合劃分：

  1.隻選一個物品：a[i]

  2.選不止一個物品，即從以下情況選

   a[i-1] + a[i]

   a[i-2] + a[i-1] + a[i]

   …

   a[1] + a[2] + … + a[i-1] + a[i]

   -> 将a[i]去掉，即為f[i-1]的情況，故該集合可看成f[i-1] + a[i]

 ->狀态轉移方程 f[i] = max(a[i], f[i - 1] + a[i])

對于每個f[i]對應的區間，不會有交集

 因題目要求若隻有負數，最大值為0，故f[i]小于0的情況直接省去

 故若有交集時，兩個集合都大于等于0

 則可以合并成新的更大的區間，或起點更靠左的區間，與目前情況不符

 故無交集

 是以可以在更新res的時候，更新左右端點

 隻有在f[i]嚴格大于res的時候更新，可以保證最大值區間的左端點最靠左，右端點最靠右

 若f[i - 1]小于0，說明i前面的數都是負數，應更新起點st

代碼及解析：

#include <iostream>
using namespace std;

const int N = 10010;
int f[N], a[N], n;
int res = -1, l, r, st = 1;	//st是目前區間的起點

int main()
{
    cin >> n;
    for ( int i = 1; i <= n; i ++ ) cin >> a[i];
    
    for ( int i = 1; i <= n; i ++ )     //dp
    {
        if ( f[i - 1] < 0 ) f[i] = 0, st = i;   //i前面的數都是負數，不取，更新起點
        f[i] = max(f[i - 1] + a[i], a[i]);      //狀态轉移
        if ( f[i] > res )   //更新最大值答案，對應更新區間
        {
            l = a[st], r = a[i];    //注意是值不是下标
            res = f[i];
        }
    }
    if ( res < 0 ) res = 0, l = a[1], r = a[n]; //全是負數的情況，按題目要求輸出
    cout << res << ' ' << l << ' ' << r;
    return 0;
}
           

end