[珂泰]16-成長最長の部分数列

3345 ワード
CodingTest テキストリンク

最も長い部分数列(11053)



数列Aを与えた場合、最長増分部分数列を求める問題.
LISとも呼ばれます.
部分数列?数列を選択して作成した数列.
数列の数値の順序は変更できません.
  • 数列Aの長さ:N、可能な部分数列は2^N種

  • 連続性を扱うためには,最後の数が何であるかが重要である.
    D[i][j]->iは長さであり、jは最後の数である.

  • 既存の数を利用しているので,1次元解が可能である.
    どんな方法で来るのかわからないわけではないので、jはいりません.

  • D[i] = A[1], ....A[i]に列挙する場合、最後のA[i]を増分した最長部分の列の長さ.

  • D[i]にはA[i]を含める必要があります.

  • 一番長い部分の数列はA[?]で、A[?], ... ,A[j],A[i]で重なる部分を探してみます.

  • D[i]=A[1]~A[i],A[i]を最後のLISの長さとする.
    • D[i]=max(D[j])+1 (j時間の複雑さ.
    問題の個数=N.
    解答時間=N
    O(N^2) 
    import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]= new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		int d[]=new int[n];
		
		for(int i=0;i<n;i++) {
			d[i]=1;
			for(int j=0;j<i;j++){
				if(a[j] < a[i] && d[i] < d[j]+1) {
					d[i] = d[j]+1;
				}
			}
		}
		int res =d[0];
		for(int i=0;i<n;i++) {
			res = Math.max(d[i], res);
		}
		System.out.println(res);
	}
}

    最も長い部分の列4



    LISの長さを求めて、それからLISが何なことを出力します.
    V[i]=A[i]の前の数値インデックス、すなわちA[i]の前のA[V[i]でなければ、長さが最も長い.
  • 駅を追跡して解けばいいです.
    • import java.util.*;

public class Main {
	static int a[];
	static int d[];
	static int v[];
	
	static void go(int p) {
		if(p==-1) return;
		go(v[p]);
		System.out.println(a[p]+" ");
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		a = new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		d=new int[n];
		v=new int[n];
		
		for(int i=0;i<n;i++) {
			d[i]=1;
			v[i]=-1;
			for(int j=0;j<i;j++){
				if(a[j] < a[i] && d[i] < d[j]+1) {
					d[i] = d[j]+1;
					v[i]=j;
				}
			}
		}
		
		int res =d[0];
		int p=0;
		for(int i=0;i<n;i++) {
			if(res < d[i]) {
				res = d[i];
				p = i;
			}
		}
		System.out.println(res);
		go(p);
		System.out.println();
	}
}

    連続(1912)



    n個の整数からなる任意の数列を与える.
    私たちはその中からいくつかの連続した数字を選んで、求められる和の中で最大の和を求めたいと思っています.
    ただし、数値は1つ以上選択する必要があります.

  • この問題の入力は、負の値、正の値、またはゼロ度です.
    最大の和を求めるには正数が必要です.しかし、負数計算も削除できません.
    -1も含まれていますが、3、-1、3なら正解かもしれません.

  • D[i]=iが2番目の数字で終わる最大連続.
    このように式を求めるには,iの第一手をできるだけ数える.

  • 正解:D[1]、、、、、D[N]の最大値.
    • import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		
		int d[]=new int[n];
		for(int i=0;i<n;i++) {
			d[i] = a[i];
			if(i==0) {
				continue;
			}
			if(d[i] < d[i-1] + a[i]) {
				d[i] = d[i-1] + a[i];
			}
		}
		int res = d[0];
		for(int i=0;i<n;i++) {
			res = Math.max(res, d[i]);
		}
		System.out.println(res);
	}
}
    これは崔伯俊先生のコードテストの基礎科目に基づいて書いた文章です.
    getElementsByTagNameNS
    VUE 3アプリケーション(1)-プロジェクトの作成