@@ -0,0 +1,2245 @@
+package coding4fun;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.Collections;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A/**%0A * Finds the longest increasing subsequence.%0A *%0A * %3Cpre%3E%0A * Input : %5B2, 4, 4, 5, 6, 1, 2, 7, 6, 10%5D%0A * Output: %5B2, 4, 5, 6, 7, 10%5D%0A *%0A * Input : %5B4, 4, 4, 5, 6, 1, 2, 3, 4, 7, 6, 10%5D%0A * Output: %5B1, 2, 3, 4, 7, 10%5D%0A *%0A * Input : %5B1, 2, 13, 16, 6, 7, 10%5D%0A * Output: %5B1, 2, 6, 7, 10%5D%0A * %3C/pre%3E%0A */%0Apublic class Problem47 %7B%0A    private static List%3CInteger%3E longestIncreasingSubsequence(List%3CInteger%3E nums) %7B%0A        List%3CInteger%3E max = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C nums.size(); i++) %7B%0A            List%3CInteger%3E list = longestIncreasingSubsequence(nums, i, new HashMap%3C%3E());%0A            list.add(nums.get(i));%0A            Collections.reverse(list);%0A            if (max.size() %3C list.size()) %7B%0A                max = list;%0A            %7D%0A        %7D%0A        return max;%0A    %7D%0A%0A    private static List%3CInteger%3E longestIncreasingSubsequence(List%3CInteger%3E nums, int idx,%0A                                                              Map%3CInteger, List%3CInteger%3E%3E memo) %7B%0A        if (memo.containsKey(idx)) %7B%0A            return memo.get(idx);%0A        %7D%0A        List%3CInteger%3E max = new ArrayList%3C%3E();%0A        int num = nums.get(idx);%0A        for (int i = idx + 1; i %3C nums.size(); i++) %7B%0A            if (num %3C nums.get(i)) %7B%0A                List%3CInteger%3E list = longestIncreasingSubsequence(nums, i, memo);%0A                List%3CInteger%3E newList = new ArrayList%3C%3E(list);%0A                newList.add(nums.get(i));%0A                if (max.size() %3C newList.size()) %7B%0A                    max = newList;%0A                %7D%0A            %7D%0A        %7D%0A        memo.put(idx, max);%0A        return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        System.out.println(longestIncreasingSubsequence(%0A            Arrays.asList(2, 4, 4, 5, 6, 1, 2, 7, 6, 10))); // %5B2, 4, 5, 6, 7, 10%5D%0A        System.out.println(longestIncreasingSubsequence(%0A            Arrays.asList(4, 4, 4, 5, 6, 1, 2, 3, 4, 7, 6, 10))); // %5B1, 2, 3, 4, 7, 10%5D%0A        System.out.println(longestIncreasingSubsequence(%0A            Arrays.asList(1, 2, 13, 16, 6, 7, 10))); // %5B1, 2, 6, 7, 10%5D%0A    %7D%0A%7D%0A

Add problem 47