Workday consultant

Ninja has recently joined the gym. He decides to lift dumbbells to build muscles. The rack contains dumbbells with varying weights. His strategy is to pick a dumbbell randomly from the rack and after exercising place it back to its original position. Now for the next exercise he can only pick dumbbells that are heavier and positioned right to the previously used. After completing all the exercises he has to tell the sum of weights of all dumbbells he picked to his trainer.

In order to impress his trainer he wants this sum to be as maximum as possible. As Ninja is saving energy for exercises, he asks you to help him choose dumbbells. Can you help Ninja to impress his trainer?

For example:

If the ‘RACK’ contains dumbbells with weights [5, 1,  2, 8], then the possible ways to choose dumbbells according to the given conditions are: [ 5 ], [ 1 ], [ 2 ], [ 8 ], [ 5, 8 ], [ 1, 2 ], [ 1, 2, 8 ], [ 2, 8 ].  Lifting dumbbells with weights [ 5, 8 ] gives the maximum sum of 13.

You have been given an integer array/list (ARR) of size N. You have to return an array/list PRODUCT such that PRODUCT[i] is equal to the product of all the elements of ARR except ARR[i]

 Note :

Each product can cross the integer limits, so we should take modulo of the operation. 

Take MOD = 10^9 + 7 to always stay in the limits.

Follow up :

Can you try solving the problem in O(1) space?

Again self introduction, roadmap of my career with the company.