Profits by cars

You are a car seller. You have N cars and the profit for each of the cars is given by an array P. The profit of cars are P1, P2, P3, ..., PN. Since you got a huge profit in the last month so you decide to get (N1) more sets of such cars. You already have one car. Now, you have N2 cars. Basically, there are N number of cars of each profit such as N cars for profit P1, N cars of profit P2, and so on up to N cars of profit PN.

You can perform the following operations any number of times:

  • If the last car is sold for profit P, then you can sell a car for profit Pc>P .

Note: You can select a car of any profit in the first operation as there are no cars that are sold earlier.

Find out the maximum profit that you can make.

For example, N=4 and prices are P1, P2, P3, P4. Since N is 4, therefore you can have four sets of cars and the prices are P1, P2, P3, P4, P1, P2, P3, P4, P1, P2, P3, P4, P1, P2, P3, P4 .

See the sample explanation for more details. 

Input format

  • The first line contains a single integer T denoting the number of test cases.
  • The first line of each test case consists of an integer N.
  • The second line consists of N space-separated integers P1, P2, P3, ..., PN

Output format

For each test case, print a single integer denoting the maximum amount of profit that you can make.





Sum of N over all test cases does not exceed 100000

1 2 3

Since N=3 here jetha will have 3 sets of cars so cars he will have are of profit 1,2,3,1,2,3,1,2,3.

He has three choices for the first car so suppose that he sell a car with profit 3 then he can not perform any operation as there is no car with profit greater than 3.Profit he makes is 3.

Suppose he sells a car with profit 2.On next operation he can sell a car for profit 3 as 3 is only available choice.After that he has to terminate.Profit he can make is 2+3=5.

If he sells a car at profit 1 then on next he has two choices {2,3} if he sells the next car at 3.He has to terminate and the profit he makes is 4.While If he sells a car at profit 2 on next day he can make another move and sell the car at price 3 so total profit:1+2+3=6 which is highest he can make.


Popular posts from this blog

How to pass parameters in webhook?

Access and modify all the resources of our Wiki.js using WikiJS API

Fahrenheit to Celsius