5.4 🔄 ➕ Rotate and Sum ➕ 🌀
You are given an array of integers A of length n. Your task is to rotate the array to the right k times and return the maximum possible sum of the array at each step of rotation.Formally, if the initial array is represented as A[0], A[1], A[2], ..., A[n-1], after one right rotation, the array will be A[n-1], A[0], A[1], ..., A[n-2].Let the sum of the array S_i at each step i be the sum of all elements multiplied by their current index. So, the sum S_i for the i-th rotation is: [ S_i = 0 \times A_i + 1 \times A_{i+1} + 2 \times A_{i+2} + ... + (n-1) \times A_{n-1} ] Find the maximum possible value of S_i after rotating the array k times.
Constraints
1 ≤ n ≤ 10^5
1 ≤ k ≤ 10^9
-10^9 ≤ A[i] ≤ 10^9
Input Format
First line: an integer n (the size of the array) and k (the number of rotations).Second line: n space-separated integers representing the array A.
Output Format
A single integer: the maximum sum after k rotations.
Example 1
Input:
5 3
1 2 3 4 5
Output:
40
Explanation:
The initial sum S0 for the array [1, 2, 3, 4, 5] is: [ S_0 = 0 \times 1 + 1 \times 2 + 2 \times 3 + 3 \times 4 + 4 \times 5 = 40 ] Rotating once yields the array [5, 1, 2, 3, 4], and the sum S1 is: [ S_1 = 0 \times 5 + 1 \times 1 + 2 \times 2 + 3 \times 3 + 4 \times 4 = 34 ] Rotating again yields the array [4, 5, 1, 2, 3], and the sum S2 is: [ S_2 = 0 \times 4 + 1 \times 5 + 2 \times 1 + 3 \times 2 + 4 \times 3 = 33 ] After k=3 rotations, the maximum sum is still 40, so the output is 40.
Log In to solve the Question