백준 11055번 가장 큰 증가 부분 수열

사용한 알고리즘 : DP

2중 for 구문을 돌리면서 DP를 구현했습니다.
첫 번째 for 구문에서, i 에서 dp[i] 값을 자기 자신으로 한 뒤,
다음 for 구문에서, 처음부터 자기 자신 전까지 돌리면서
dp[i] = max(dp[i], dp[j]+자기자신 값) 으로 최신화 해 주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, arr[1000], dp[1000], ans;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	cin >> arr[i];
	dp[i] = arr[i];
	for (int j=0; j < i; ++j){
	if(arr[i] > arr[j]){
	dp[i] = max(dp[i], dp[j]+arr[i]);
	}
	}
	ans = max(ans,dp[i]);
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 11055.cpp hosted with ❤ by GitHub