#11055最大増分部分数列(Bigget増分サブシーケンス)c++

1190 ワード
baekjoon algorithm LIS dynamicprogramming テキストリンク
A[i]に値を入力し、B[i]に同じ値を入力します.
Aの部分数列は増分数列である.
現在の比較値(B[i])より前の和+現在値(B[j]+A[j])より大きい場合は、この値を現在の比較値(B[i])に入れます.
コードを作るときもいつも混ざっているので、表に記入して考えます.
#include<iostream>
#include<vector>

using namespace std;

const int MAX = 1001;

int bis(int k) {

	int result = 0;
	int B[MAX];
	vector<int>A(k);

	for (int i = 0; i < k; i++) {
		cin >> A[i];
		B[i] = A[i];

		for (int j = 0; j < i; j++) {
			if (A[j] < A[i] && B[i] < B[j] + A[i])
				B[i] = B[j] + A[i];
		}

		result = max(result, B[i]);
	}

	return result;
}

int  main() {
	int k;
	cin >> k;
	cout<<bis(k)<<endl;

	return 0;
}
[Lv-1]ビット数の追加
[プログラマー-レベル2]スキルツリー[Java]