[伯俊]11055最大部分増加数列


100準11055最大部分増加数列
  • https://www.acmicpc.net/problem/11055
  • dp[i]:LIS合計
  • 、iを最後の要素とする
    #include <iostream>
    using namespace std;
    
    int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    	cout.tie(NULL);
    	
    	int dp[1001] = { 0 };
    	int A[1001] = { 0 };
    
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++)
    		cin >> A[i];
    
    	int max = A[0];
    	dp[0] = A[0];
    
    	for (int i = 1; i < n; i++) {
    		dp[i] = A[i];
    
    		for (int j = 0; j < i; j++) 
    			if (A[i] > A[j] && dp[j] + A[i] > dp[i])
    				dp[i] = dp[j] + A[i];
    		if (max < dp[i]) max = dp[i];
    	}
    
    	cout << max;
    	return 0;
    }