阿裡筆試示例：小猴子摘桃

題目描述：

小猴子下山，沿着下山的路有一排桃樹，每棵樹都結了一些桃子。小猴子想摘桃子，但是有一些條件需要遵守，小猴子隻能沿着下山的方向走，不能回頭，每顆樹最多摘一個，而且一旦摘了一棵樹的桃子，就不能再摘比這棵樹結的桃子少的樹上的桃子。那麼小猴子最多能摘到幾顆桃子呢？

舉例說明，比如有5棵樹，分别結了10，4，5，12，8顆桃子，那麼小猴子最多能摘3顆桃子，來自于結了4，5，8顆桃子的桃樹。

輸入:

輸入桃樹的數量和每棵樹的桃子數 N x1 x2 … xn

輸出:

小猴子能摘到的最多的桃子個數

輸入範例:

5

10

4

5

12

8

輸出範例:

3

思路：

最長遞增子序列問題，

首先将【10，4，5，12，8】排序，得到【4、5、8、10、12】，然後求排序前後的最長公共子序列 。

【10，4，5，12，8】與【4、5、8、10、12】的最長公共子序列是【4，5，8】或【4、5、10】或【4、5、12】，反正最長遞增子序列的長度都是3，這道題我們求長度即可。

public class Main{

    static int pick(int[] peaches) {
        int[] arr = peaches.clone();
        Arrays.sort(arr);
        int[][] dp = new int[arr.length+1][arr.length+1];
        for(int i = 1; i <= arr.length; i++) {
            for(int j = 1; j <= arr.length; j++) {
                if(arr[i-1] == peaches[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[arr.length][arr.length];
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int trees = Integer.parseInt(in.nextLine().trim());
        int[] peaches = new int[trees];
        for (int i = 0; i < peaches.length; i++) {
            peaches[i] = Integer.parseInt(in.nextLine().trim());
        }
        System.out.println(pick(peaches));
    }
}