73 数字游戏2

动态规划+贪心

#include <iostream>  

using namespace::std;
using std::cout;
using std::cin; 

int n;
int nums[500100],dp[500100];

int szyx2(int n, int nums[]) 
{
    int result = 0;
    for(int i=0; i<n; i++)
	{
        for(int j=0; j<i; j++)
		{
            if(nums[j] < nums[i])
			{
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
        result = max(result,dp[i]+1);
        if(result >= 3)
        {
        	i=n;
        	result=3;
		}
    }
    return result;
}

int main() 
{
    cin >> n;
    for(int i=0; i<n; i++)
    {
    	cin >> nums[i];
	}
    if(szyx2(n, nums) == 3)
    {
    	std::cout << "true";
	}
	else
	{
		std::cout << "false";
	}
    return 0;  
}