Maximum Partitions :
Difficulty Level : Easy
Submissions : 300
Asked In :
Marks :10
: 2 | : 1
You are given an array $$$a$$$ consisting of $$$n$$$ integers. You can make any number of partitions in the array such that when you combine all these partitions, the value of the special sum that is obtained is maximum. If you make $$$k$$$ partitions in the array, the the special sum is defined as $$$P_{1} - P_{2} + P_{3} + .... + (-1)^{k+1}P_{k}$$$. Here $$$P_{i}$$$ is defined as the summation of all integers in that partition.
The first line of input consists of a single integer $$$n$$$ - the total number of elements in the array. The next line consists of $$$n$$$ space separated integers - the elements of the array a. $$$(-10^9 \leq a[i] \leq 10^9)$$$.
Output a single integer - the maximum special sum that can be obtained by partitioning the array.
3 1 -2 3
6
