Max Subsequence

一个sequence，里面都是整数，求最长的subsequence的长度，使得这个subsquence的最大值和最小值相差不超过1. 比如[1,3,2,2,5,2,3,7]最长的subsequence是[3,2,2,2,3],所以应该返回5.

分析：

这题可以先排序，然后找出两个相差1的相邻值的最大长度。第二种方法可以用HashMap，保存每个值出现的个数，然后从当前值往下找比当前值大1的数出现的个数。

 　　public int maxSequence(int[] arr) {

         if (arr == null || arr.length == )

             return ;

         Map<Integer, Integer> map = new HashMap<>();

         for (int key : arr) {

             map.put(key, map.getOrDefault(key, ) + );

         }

         int max = ;

         for (int key : arr) {

             max = Math.max(max, map.get(key) + map.getOrDefault(key + , ));

         }

         return max;

     }

巴特西

Max Subsequence

最新文章

热门文章