Maximum Weighted Subsequence - Mastercard Online Assessment

Problem Preview

"You are given an array `A` of `N` integers and an integer `K`. Select a subsequence of exactly `K` elements from the array while preserving their original order. If the selected elements are `B1, B2, ..., BK`, then the score of the subsequence is [ \sum_{i=1}^{K} i \times B_i ] Find the maximum possible score. ### Input The first line contains two integers `N` and `K`. The second line contains `N` integers `A1, A2, ..., AN`. ### Output Print the maximum possible score. ### Constraints * `1 ≤ K ≤ N ≤ 3000` * `-10^9 ≤ Ai ≤ 10^9` ### Example **Input** ``` 5 3 3 5 2 6 4 ``` **Output** ``` 29 ``` ### Explanation Choose the subsequence `[5, 6, 4]`. Score ``` 1×5 + 2×6 + 3×4 = 5 + 12 + 12 = 29 ``` ---"