最长上升子序列

题目描述

广场上站着一支队伍，她们是来自全国各地的扭秧歌代表队，现在有她们的身高数据，请你帮忙找出身高依次递增的子序列。 例如队伍的身高数据是（1、7、3、5、9、4、8），其中依次递增的子序列有（1、7），（1、3、5、9），（1、3、4、8）等，其中最长的长度为4。

输入描述:

输入包含多组数据，每组数据第一行包含一个正整数n（1≤n≤1000）。

紧接着第二行包含n个正整数m（1≤n≤10000），代表队伍中每位队员的身高。

输出描述:

对应每一组数据，输出最长递增子序列的长度。

输入例子:

7
1 7 3 5 9 4 8
6
1 3 5 2 4 6

输出例子:

4
4

最长上升子序列(Longest Increasing Sub-sequnce)是一个常见的题目。常见的做法有两种：
方法一：复杂度为O(n^2)，动态规划。
方法二：复杂度为(n*log(n)),动态规划。
具体参见文献：
http://yzmduncan.iteye.com/blog/1546503

import java.util.Scanner;

/**
 * Created by fang on 2015/9/19.
 */
class Solution {
  
    public int longestIncreasingSubS(int[] nums) {
        int[] maxLen = new int[nums.length];
        int result = 1;

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

        for (int i = 1; i < nums.length; i++) {
            int max = 0;
            for (int j = 0; j <= i - 1; j++) {

                if ((nums[j] < nums[i]) && (maxLen[j] > max))
                    max = maxLen[j];

            }

            maxLen[i] = max + 1;
            if (maxLen[i] > result)
                result = maxLen[i];
        }

        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            Solution sln = new Solution();
            System.out.println(sln.longestIncreasingSubS(nums));
        }
    }
}