Question

Kvalues inside array < 109
There is an array of N integers. You are required to make any number of partitions in the array such that the special sum o
all the partitions combined is maximized.
If you make K partitions then the Special Sum is defined as P1 – P2 + P3 – P4 + P5.....+(-1)(K-1) P2
Here P; is defined as the summation of all integers in that partition.
Input format
The first line consists of an integer N that denotes the number of integers in the array.
The second line consists of N integers that denote the values of the array.
Output format
Print aa single integer which denotes the maximum value of the special sum that can be obtained by any number of
partitions.
Constraints
1<N< 100000
-10^9<_ values inside array<_10^9

input
5
1 -2 -3 2 1

output
9​

Answer 1

Answer:

10,[5,3,7]},{[10,5],[3,7},{[10,5,3],7}

and

{[10,5],[3,7} is the optimal one.