CODEWITHSUNDEEP
data-structureslogic
Nilesh Gupta
Nilesh Gupta

Reputation: 11

Minimum value of prefix sum of array with integer values

Given an array like [3,4,6,1,1]. Arrange it in such a way that it's prefix sum gives minimum value for the expression given below. prefix sum array will be [3,7,13,14,15] We have to calculate it's value like 3-7+13-14+15=10 so arrange the original array in such a way that this value is minimized

Upvotes: 1

Views: 443

Answers (1)

stf
stf

Reputation: 621

I will give you a hint.

Let's suppose the output array is of the form: [p1, p2, ... pn]. In your example, the 5-element output array is of the form: [p1, p2, p3, p4, p5]. Then the resulting expression value is:

+p1
-p1-p2
+p1+p2+p3
-p1-p2-p3-p4
+p1+p2+p3+p4+p5

which is: +p1+p3+p5. Now you only have to minimize this sum, which you can easily do for example by sorting the input array and selecting the 3 smallest elements and placing them at positions 1, 3 and 5. The remaining elements and the ordering do not matter.

If the input array is of even length, you do it in a similar way. For example (length=4):

+p1
-p1-p2
+p1+p2+p3
-p1-p2-p3-p4

Result: -p2-p4. So here you have to select the 2 biggest elements and place them at positions 2 and 4.

Does this make sense? Do you know how to code this in the general case?

Upvotes: 2

Related Questions