Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int n;
- int niza[10050];
- int dp[10050][2];
- int fc(int i, int razlika){
- if(i==n){
- return 0;
- }
- if(dp[i][razlika]!=-1){
- return dp[i][razlika];
- }
- int result=0;
- if(razlika==0){
- for(int j=i+1; j<n; j++){
- if(niza[i]-niza[j]>0){
- result=max(result, fc(j, 1)+1);
- }
- }
- }
- if(razlika==1){
- for(int j=i+1; j<n; j++){
- if(niza[i]-niza[j]<0){
- result=max(result, fc(j, 0)+1);
- }
- }
- }
- return dp[i][razlika] = result;
- }
- int main()
- {
- cin>>n;
- for(int i=0; i<n; i++){
- cin>>niza[i];
- dp[i][0] = dp[i][1] =-1;
- }
- int cikcak=0;
- for(int i=0; i<n; i++){
- cikcak=max(cikcak, fc(i, 0));
- cikcak=max(cikcak, fc(i, 1));
- }
- cout<<cikcak + 1 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement