Find Subsequence of Length K With the Largest Sum
给一个数组, 求一个和最大的长度为k的子序列.
这有三个定语, 长度为k, 子序列, 和最大. 我用的是做一个pair<坐标, 数字>, 然后排序两次.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public int[] maxSubsequence(int[] nums, int k) { List<Pair> pl= new ArrayList<>(); for(int i = 0; i < nums.length; i++) pl.add(new Pair(i, nums[i])); Collections.sort(pl, (a,b) -> (b.s - a.s)); List<Pair> spl= new ArrayList<>(); for(int i = 0; i < k; i++){ spl.add(pl.get(i)); } Collections.sort(spl, (a,b) -> (a.f - b.f)); int[] res = new int[k]; for(int i = 0; i < k; i++){ res[i] = spl.get(i).s; } return res; } class Pair{ int f; int s; public Pair(int f, int s){ this.f = f; this.s = s; } } } |