All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

Array Splitting into two parts <P2SME>
Tag(s):

Algorithms, Dynamic Programming, Medium, Two dimensional

Problem
Editorial
Analytics

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 \(Part 1\).

Let \(g(x)\) denote sum of the elements in \(Part 2\).

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 :

\(1 \le N \le 100\)

\(1 \le A[i] \le 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.

SAMPLE INPUT
4
2 3 5 6
SAMPLE OUTPUT
64
Explanation

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

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Power2SME

Challenge Name

Power2SME PHP Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?