Array Splitting into two parts <P2SME>

4.4

5 votes
Algorithms, Dynamic Programming, Medium, Two dimensional
Problem

You are given an array of size N. Distribute the elements of the array into two parts such that the product of the sum of two parts is maximum.

In other words,

Let f(x) denote sum of the elements in Part1.

Let g(x) denote sum of the elements in Part2.

You need to maximise f(x)g(x)

Input :
First line contains an integer N, denoting number of elements in array.
Next line contains N integers denoting the array elements.

Output :

Maximum value of f(x)g(x).

Constraints :

1N100

1A[i]500


Note: It is not mandatory to use the code snippet that is provided to you in the editor by default. It is just to make the question more convenient. You can completely remove the default code and submit your solution in the appropriate format.

Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Maximum product is possible when part 1 contains 2,6 and part 2 contains 3,5

Editor Image

?