[テストコードC+]連続

今日の質問

https://www.acmicpc.net/problem/1912

れんけつ

方法

ターゲットは出力

の連続和の中で最大である.

入力値は100000であるため、最大O(Nlong N)のアルゴリズムを記述することができる.

dpを使って、O(N)だけで問題を解くことができます.

単純に和を求め、保存し、和が元の値より小さい場合は大きな元の値を保存します.

の結果の最大値を出力します.

なぜそうなるのか、連続的に増加しても小さくなる部分があれば、そこから始め、反映しないべきだ.

右側が最大値で、左側が小さくなる部分があれば、無条件に最大値より小さくなるからです.

私の答え

#include <iostream>
using namespace std;
const int MAX = 100000;
int arr[MAX+1] ={0, };
int dp[MAX+1] ={0, };
int n;

int solution(){
    int answer = arr[1];
    for(int i=1;i<=n;i++){
        dp[i] = max(dp[i-1] + arr[i], arr[i]);
        answer = max(answer, dp[i]);
    }
    return answer;
}

別の解釈

#include<iostream>
using namespace std;
int main() {
	int N,max=-1000;
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	cin>>N;
	for(int i=0,t=0,b;i<N;i++){
		cin>>b;
		b=t+b>b?t+b:b;
		max=max<b?b:max;
		t=b;
	}
	cout<<max;
}

学ぶべきところ

別の

を見ると、入力に時間を減らす方法がたくさんあります.

こちらは

で、入力した値と最大値を利用して問題を解きます.いずれにしても使用するdpは以前の値しかないので可能です.