最长递增子序列A

[编程题]最长递增子序列A

热度指数：3468 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.

输入描述:


第一行包含一个整数T，代表测试数据组数。

对于每组测试数据：
N-数组的长度

a1 a2 ... an （需要计算的数组）

保证：

1<=N<=3000,0<=ai<=MAX_INT.

输出描述:

对于每组数据，输出一个整数，代表最长递增子序列的长度。

示例1

输入

2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出

3
3

算法知识视频讲解

查看答案及解析

Java

ZhanHeng

import java.util.*;

public class Main{
    public static int getLIS(int[] arr) {
		int[] dp = new int[arr.length];
		int[] ends = new int[arr.length];
		ends[0] = arr[0];
		dp[0] = 1;
		int right = 0;
		int l = 0 , r = 0 , m = 0;
		for (int i = 1; i < arr.length; i++) {
			l = 0;
			r = right;
			while (l <= r) {
				m = (l + r) / 2;
				if (arr[i] > ends[m]) {
					l = m + 1;
				} else {
					r = m - 1;
				}
			}
			right = Math.max(right, l);
			ends[l] = arr[i];
			dp[i] = l + 1;
		}
        //以上是获取dp数组，引入辅助数组+二分查找，复杂度O(NlogN)
        int len = 0;
		for (int i = 0; i < dp.length; i++)
			if (dp[i] > len) 
				len = dp[i];
		return len;
	}

    public static void main(String[] args){
         Scanner in = new Scanner(System.in);
         while (in.hasNextInt()) {
            int t = in.nextInt();
            while(t--!=0){
               int n = in.nextInt();
               int[] arr = new int[n];
               for(int i=0 ; i<n ; i++){
                   arr[i] = in.nextInt();
               }
               System.out.println(getLIS(arr));
             }
        }
    }
}

编辑于 2016-09-07 23:32:46 回复(0)

Java

克逊

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			int count = in.nextInt();
			
			for (int i=0; i<count; i++) {
				int length = in.nextInt();
				int[] array = new int[length];
				int[] values = new int[length];
				for (int j=0; j<length; j++) {
					array[j] = in.nextInt();
				}
				
				findMaxSLength(array, values);
			}
		}
	
	}
	
	public static void findMaxSLength(int[] array, int[] values) {
		
		int length = array.length;

		for (int i=0; i<length; i++) {
			if (i==0) {
				values[i] = 1;
			} else {
				
				int max = 0;
				for (int j=i-1; j>=0; j--) {
					if (array[j] < array[i]) {
						int temp = values[j] + 1;
						if (temp > max) {
							max = temp;
						}
					}
					values[i] = max == 0?1:max;
				}
				
			}
		}
		
		int max=0;
		for (int k : values) {
			if (k>max) {
				max = k;
			}
		}
		System.out.println(max);
	
	}

}

发表于 2016-07-24 11:48:17 回复(0)