题解 | #最长上升子序列(一)# c++ && java

//本题用动态规划解决 ，建议看我合唱队的那篇题解1，写的很详细，这次就偷个懒了

#include <bits/stdc++.h>
using namespace std;

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int length = 0;
    cin>> length;

    int inits[length];
    for (int i = 0; i < length; ++i) {
        cin>>inits[i];
    }

    int dp2[length];

    for (int i = 0; i < length; ++i) {
        dp2[i] = 1;
    }


    int minNumber = 1;
    for (int i = 1; i  < length ; i++) {
        for (int j = 0; j < i ; j++) {
            if (inits[i] > inits[j]){
                dp2[i] = max(dp2[i],dp2[j] +1 );
            }
        }
        minNumber = max(minNumber,dp2[i]);
    }

    cout<<minNumber<<endl;
}

import java.io.*;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) throws IOException {
	  StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	  PrintWriter printWriter  = new PrintWriter(new OutputStreamWriter(System.out));
	  streamTokenizer.nextToken();
	  int nums = (int) streamTokenizer.nval;
	  int[] ints = new int[nums];
	  for (int i = 0; i < nums; i++) {
		  streamTokenizer.nextToken();
		  ints[i] = (int) streamTokenizer.nval;
	  }

	  int[] dp = new int[nums];
	  Arrays.fill(dp,1);
	  int Max = 1;

	  for (int i = 1; i < nums; i++) {
		  for (int j = 0; j < i ; j++) {
			  if (ints[i] > ints[j]){
				  dp[i] = Math.max(dp[i],dp[j]+1);
			  }
		  }
		  Max = Math.max(Max,dp[i]);
	  }

	  printWriter.println(Max);
	  printWriter.flush();
}

}