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

1826 ワード
百駿オンライン阻止 テキストリンク

今日の質問


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は以前の値しかないので可能です.
    • Letcode 57挿入間隔
    Activityインタフェースのデジタルスケジュール