解いた問題のソースコードと解説など。


POJ 2593 Max sequence

問題文

DP強化週間。

要素数Nの配列a[]が与えられた時、
{S=max_{1 \le i \le j \lt p \le q \le N}{\sum_{t=i}^{j}{a_t} + \sum_{t=p}^{q}{a_t}}}
のSを求める。

N <= 100000 で複数のデータが与えられるのでO(N^2)では間に合わない。
dp[i]:=(i番目までで最大の区間和)とする。

これを配列の左端から計算したものdp_lと
右端から計算したdp_rを求め、iを走査してmax(dp_l[i] + dp_r[i + 1])を求めれば良い。

int l[100001];
int r[100001];
int dp_l[100001];
int dp_r[100001];
int a[100000];

int main(int argc, char **argv){
  int N;
  while(scanf("%d", &N), N){
    for(int i = 0; i < N; i++) scanf("%d", &a[i]);

    int lmax = l[0] = dp_l[0] = a[0];
    for(int i = 1; i < N; i++){
      l[i] = a[i] + max(l[i - 1], 0);
      if(lmax < l[i])
	lmax = l[i];
      dp_l[i] = lmax;
    }

    int rmax = r[N - 1] = dp_r[N - 1] = a[N - 1];
    for(int i = N - 2; i >= 0; i--){
      r[i] = a[i] + max(r[i + 1], 0);
      if(rmax < r[i])
	rmax = r[i];
      dp_r[i] = rmax;
    }

    int ans = -INF;
    for(int i = 0; i < N - 1; i++)
      ans = max(ans, dp_l[i] + dp_r[i + 1]);

    cout << ans << endl;
  }
  return 0;
}

忙しくなってきた。

しょげないでよBaby 眠れば治る