Есть ли способ, которым я могу решить этот вопрос в nlogn сложности

Question

Вам дана последовательность из N целых чисел A, обозначаемых A [1], A [2]… ..A [N]. Каждое целое число в последовательности имеет значение, связанное с ним W [1], W [2]…. W [N]. Вы должны выбрать подпоследовательность данного массива A так, чтобы все элементы в A были в строго возрастающем порядке, а сумма значений элементов в этой выбранной подпоследовательности была максимальной. Вы должны напечатать это максимальное значение.

Sample Input

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

Sample Output

1000   
100     

Я пытался решить эту проблему с помощью динамического программирования c, но временная сложность моего кода n ^ 2, поэтому я хочу уменьшить его сложность до nlogn. Можете ли вы мне помочь?

Вот моя реализация:

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);
    }
}

Я получаю TLE из-за ограничений

Ограничения 1 <= T <= 5 1 <= N <= 200000 1 <= a [i] <= 10 ^ 9, где i ∈ [1..N] 1 <= w [i] <= 10 ^ 9, где i ∈ [1..N] </p>

Answer 1

Выполните итерацию один раз и сохраняйте TreeMap суммы значений W для значений A, меньших или равных данному A, как видно на момент итерации по значению A.

Для new A, вызовите метод lowerEntry(key) для суммы W ниже этой новой A.

Запомните наибольшую сумму и верните ее.

Одна итерация равно O (n) , а TreeMap используется: O (log n) , поэтому решение равно O (n log n) ^*.

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;
}

^{*) Внутренний for l oop - это O (log n) (амортизированный, наихудший случай), поэтому он не влияет на общую сложность .}

Тест

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