题目描述 : Redraiment是走梅花桩的高手。Redraiment总是起点不限，从前到后，往高的桩子走，但走的步数最多，不知道为什么？你能替Redraiment研究他最多走的步数吗？
样例输入
6
2 5 1 5 4 5
样例输出
3
提示
Example:
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5
从第5格开始走最多有2步,4 5
所以这个结果是3。
输入例子:
6
2
5
1
5
4
5
输出例子:
3
//求不连续的最长递增子序列
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner; public class Main { public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt())
{
int num = in.nextInt();
int array[] = new int[num];
for(int i = 0; i<num; i++)
{
array[i] = in.nextInt();
}
int max = GetResult(num, array);
System.out.println(max);
}
}
public static int GetResult( int num, int[] pInput)
{
//求不连续的最长递增子序列
int result[] = new int[num];//存放当前位置的最长字串长度
for(int i = 0;i<pInput.length;i++)
{
result[i] = 1;
for(int j = 0; j<i; j++)
{
if(pInput[j] < pInput[i])
{
result[i] = Math.max(result[i], result[j]+1);
}
}
}
int max = 0;
for(int i = 0;i<result.length;i++)
{
if(result[i] > max){max = result[i];}
}
return max;
}
}