Question 10

Problem Statement

Question 10 Problem Description Given is an array of a size n. Among all strictly increasing subsequences of a, find any one with the maximum possible sum of elements. A subsequence of a is defined as a sequence that can be obtained from a by deleting some elements (possibly none), without changing the order of the remaining elements. The array a is said to be a strictly increasing sequence if a[i] Input Format The first line contains an integer t, the number of test cases. For each test case: The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers a₁, a₂, ..., aₙ, the elements of the array. Constraints 1 ≤ t ≤ 1000 1 ≤ n ≤ 200,000 -10^9 ≤ a_i ≤ 10^9 for all valid i The sum of n over all test cases does not exceed 200,000. Output Format For each test case, print the maximum possible sum of a strictly increasing subsequence on a new line. Sample Input 2 4 6 1 2 3 7 4 2 5 5 3 1 6 Sample Output 6 15 E