有没有办法用nlogn复杂度来解决这个问题

Question

给出一个由N个整数a组成的序列，用a[1]，a[2]….a[N]表示。序列中的每个整数都有一个与其相关联的值W[1]，W[2]……。W[N]。你必须选择给定数组a的一个子序列，使a中的所有元素都是严格递增的，并且在这个选定的子序列中元素的值之和是最大的。你必须打印这个最大值。

样本输入

2  
4  
1 2 3 4  
100 200 300 400  
3  
4 2 3  
100 30 20   

1000   
100     

public class testing {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int t = scn.nextInt();
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = scn.nextInt();
            int a[] = new int[n];
            long val[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = scn.nextInt();
            }
            for (int i = 0; i < n; i++) {
                val[i] = scn.nextLong();
            }

            long dp[] = new long[n];
            Arrays.fill(dp, Integer.MIN_VALUE);
            dp[0] = val[0];
            for (int i = 1; i < n; i++) {
                for (int j = i - 1; j >= 0; j--) {
                    if (a[j] < a[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + val[i]);
                    }
                }
            }
            long ans = Integer.MIN_VALUE;
            for (long v : dp) {
                ans = Math.max(v, ans);
            }
            sb.append(ans + "\n");
        }
        System.out.println(sb);
    }
}

我因为对比关系而变得很虚弱

约束1<=T<=51<=N<=2000001<=a[i]<=10^9,其中i∈[1...N]1<=w[i]<=10^9,其中i∈[1...N]

Answer 1

迭代一次，并为小于或等于给定a的a值维护W值之和的treemap，就像在迭代a值时看到的那样。

对于新的a，调用LowerEntry(key)方法以获得该新a下面W的和。

记住最大的总和，然后返回。

static int sumIncreasing(int[] a, int[] w) {
    int maxSum = Integer.MIN_VALUE;
    TreeMap<Integer, Integer> sums = new TreeMap<>();
    for (int i = 0; i < a.length; i++) {
        Entry<Integer, Integer> lowerSum = sums.lowerEntry(a[i]);
        int sum = (lowerSum != null ? lowerSum.getValue() + w[i] : w[i]);
        sums.put(a[i], sum);
        for (Entry<Integer, Integer> e; (e = sums.higherEntry(a[i])) != null && e.getValue() <= sum; )
            sums.remove(e.getKey());
        if (sum > maxSum)
            maxSum = sum;
    }
    return maxSum;
}

System.out.println(sumIncreasing(new int[] {1, 2, 3, 4}, new int[] {100, 200, 300, 400}));
System.out.println(sumIncreasing(new int[] {4, 2, 3}, new int[] {100, 30, 20}));

输出

1000
100