掃瞄線演算法

掃瞄線演算法

P-4-13. 最大連續子陣列

輸入一個整數陣列 A[1:n]，請計算 A 的連續子陣列的最大可能總和，空陣列的和以
0 計算。
Time limit: 1 秒
輸入格式：第一行是正整數 n，第二行有 n 整數 A[1], A[2], …, A[n]。n 不超
過 1e5，陣列內容絕對值不超過 1e9。
輸出：最大可能總和。

範例一輸入：
8
4 12 -17 5 8 -2 7 -3

範例一輸出：
18

範例二輸入：
3
-1 -1 -1

範例二輸出：
0

  1 2 3     -6 2 -3    -3 6 9
| =6 需要 | =-7 不需要| =12 需要

我們可以把每個區間看成一個部分，如果這個區間是正的，代表我們需要他

d784. 一、連續元素的和

考慮要不要前面

#include <iostream>
using namespace std;
#define nn "\n"
#define N 1000

int main(){
    int w;
    cin>>w;
    while(w--){
        int n;
        cin>>n;
        int dp[N];
        int ans=-100000;
        cin>>dp[0];
        if(dp[0]<0){
            dp[0]=0;
        }
        for(int i=1;i<n;i++){
            cin>>dp[i];
            if(dp[i-1]>0){
                dp[i]+=dp[i-1];//前面是有用的才拿
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<nn;
    }
}

expandcollapse

考慮選、不選

#include <iostream>
using namespace std;
#define nn "\n"
#define N 1000

int main(){
    int w;
    cin>>w;
    while(w--){
        int n;
        cin>>n;
        int dp[N];
        int ans=-100000;
        cin>>dp[0];
        if(dp[0]<0){
            dp[0]=0;
        }
        for(int i=1;i<n;i++){
            cin>>dp[i];
            dp[i]+=dp[i-1];
            ans=max(ans,dp[i]);
            dp[i]=max(dp[i],0);
        }
        cout<<ans<<nn;
    }
}

expandcollapse