C Programming Language

Problem Title: Jojos Hardest Problem (?)

SOLVE WITH THE VERY EFFICIENT CODE BECAUSE BELOW IS THE LINK THAT THE LOGIC IS CORRECT, BUT GOT TIMELIMIT VERDICT

LINK : https://www.chegg.com/homework-help/questions-and-answers/c-programming-language-problem-title-jojo-s-hardest-problem-jojo-enjoying-vacation-family--q43949702?trackid=BED26UHo

Jojo is enjoying his vacation with his family. Suddenly an instant message came in. Apparently there is a message from Lili : Jojo, dont forget to check the forum. Who knows if there is an assignment before the exam

Jojo finally took the time to check the discussion forum and sure enough, there were some assignments given to his class. He immediately told his classmates. Jojo finds out one difficult problem for himself as follows. Given an array contains N elements and also given an integer M. You need to find a value of a function f(x, k) so that the function has value as maximum as possible but still less than or equal to M. Value of k is arbitrary as the value less than or equal to N. The function f(x, k) is expressed as below.

f(x, k) = A[x] k + A[x + 1] (k 1) + ... + A[x + k 1] 1

Help Jojo to get the right final answer.

Format Input

Input consists of an integer T that indicates the number of test case. Then, 3 lines follow. The first line contains an integer N as the number of elements in array. The next one is describing the value N elements A[i] in the array and followed by an integer M on the third line.

Format Output

Output should be expressed in format Case #X: Y - X is the number of the test case, and followed by Y , the maximum value of function f(x, k) such k arbitrary value that less than or equal to N for X^th case.

Constraints

1 T 100 1 N 100000 1 A[i] 1000000 0 M 1000000000000000000

SOLVE WITH THE VERY EFFICIENT CODE

Sample Input & Output (standard input & output)

2

5

6 1 3 4 6

10

Case #1: 10

5

1 2 3 4 5

14

Case #2: 13

PLEASE SOLVE IN LESS THAN O(n^2) TIME

Explanation For test case 1, the maximum result is

f(3, 2) = 3 2 + 4 1 = 10.

PLEASE SOLVE WITH THE VERY EFFICIENT CODE