Incrementing Subarrays

4.6

5 votes
Dynamic Programming, Algorithms, 2D dynamic programming
Problem

You are given an array A of length N. You are also given an integer, K. You can increment all elements of any subarray of A by K, at most once.

Let us define the score of A as the sum of A[i]%A[i1], for all i in the range [1,N1]. Find the maximum possible score you can obtain.

Input Format:

  • The first line of input contains a single integer T, which denotes the number of test cases.
  • The first line of each testcase contains two integers, N and K, denoting the length of the array A, and the increment amount respectively.
  • The second line of each testcase contains N integers, denoting the array A.

Output Format:

For each test case, print the maximum possible score you can obtain.

Constraints:

1<=T<=10

2<=N<=105

1<=A[i],K<=109

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

First test case:
If we increment the whole array by K=1, the array becomes [6,5,4].
The score of this array is (5%6)+(4%5)=5+4=9.
It can be shown that this is the maximum possible score. Thus, the answer is 9.

Second test case:
If we do not increment any subarray, the score of A is 11%7=4.
It can be shown that this is the maximum possible score. Thus, the answer is 4.

Editor Image

?