Max - Min

Moderate

0/80

Average time to solve is 30m

Contributed by

0 upvote

Problem statement

Ninja is given an array ‘A’ of size ‘N’. He needs to divide this array into exactly four non-empty and non-overlapping contiguous parts, such that the difference between maximum and minimum of the sum of elements of all those four parts is minimum.

For example:

Let’s say N = 5 and A[] = {3, 2, 4, 1, 2}. 
So if we divide the array into four parts as {3}, {2}, {4} and {1, 2}, then the sum of all the elements of these parts is 3, 2, 4, and 3. Here the difference between the maximum and minimum of these parts sum is (4 - 2) = 2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format-

First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first contains a single integer 'N' denoting the size of the array.
The second line contains 'N' space-separated integers denoting the elements of the array 'A.'

Output Format-

For each test case, you have to print the minimum difference between the maximum and minimum sum of elements of divided four parts.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints -

1 <= ‘T’ <= 5
4 <= ‘N’ <= 10^5
0 <= ‘A[i]’ <= 10^5

Time Limit: 1 sec

Sample Input-1

Sample Output-1

2
13

Explanation for Sample Input 1:

For test case 1:
    If we divide the array into four parts {3}, {2}, {4} and {1, 2}, then the sum of all the elements of these four parts is 3, 2, 4, and 3. Here the difference between the maximum and minimum of these parts sum is (4 - 2) = 2.
For test case 2:
    If we divide the array into four parts {14}, {6}, {1} and {7}, then the sum of all the elements of these four parts is 14, 6, 1, and 7. Here the difference between the maximum and minimum of these parts sum is (14 - 1) = 13.

Sample Input -2

2
10
10 71 84 33 6 47 23 25 52 64
7
1 2 3 10000 4 5 6

Sample Output -2

36
9994

Console