Given, an array arr[] of N integers, the duty is to pick some integers from this array arr[] and prepare them in one other array brr[], such that the sum of brr[i]*(i+1) for each index in array brr is most. Discover out the utmost doable such worth for a given array arr.
Enter: N = 5, arr[] = {-1, -8, 0, 5, -9}
Output: 14
Clarification: By deciding on -1, 0, and 5 we’ll get the utmost doable worth.(-1*1 + 0*2 + 5*3 = 14)Enter: N = 3, arr[] = {-1, -8, -9}
Output: 0
Clarification: Since all of the numbers are detrimental it’s higher to not choose any quantity.
Strategy: To resolve the issue comply with the beneath thought:
The issue might be solved utilizing a grasping strategy. The instinct behind the grasping strategy is that the utmost worth is obtained by deciding on the most important quantity first, and the smallest quantity final. By sorting the array in lowering order, we will be sure that we’ve the most important quantity at first, and thus maximize the worth.
Steps that had been to comply with the above strategy:
- First, we kind the enter array in lowering order.
- Then, we iterate over the array and calculate the prefix sums of the weather, including every prefix sum to the consequence so long as it stays non-negative.
- If the prefix sum turns into detrimental at any level, we cease the iteration and return the present consequence.
- By stopping the iteration as quickly because the prefix sum turns into detrimental, we will be sure that we don’t choose any numbers which have a internet detrimental contribution to the entire worth. This enables us to acquire the utmost worth.
Under is the code to implement the above strategy:
Python3
|
|
Time Complexity: O(N*logN), the place N is the size of the array.
Auxiliary Area: O(1), as we aren’t utilizing any further area.
