Magic of Square

★★★★★

4 votes

Dynamic programming, Introduction to Dynamic Programming 1, Arrays, Dynamic Programming, Algorithms, Medium, Greedy algorithm

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ of integers. You have to select an integer $a$ from the array, square it, and then return the sum of the subarray that has the maximum sum over all subarrays of the resultant array.
You have to select an integer $a$ such that you can maximize the final answer.

Note: The sum of a subarray is the sum of all the integers in the subarray.

Input format

First line: $n$ denoting the length of the array $A$
Second line: $n$ space-separated integers of the array $A$

Output format

In a single line, print a single integer denoting the sum of the subarray that has the maximum sum over all subarrays of $A$ after changing one integer to its square.

Input Constraints

$1 \leq n \leq 500000$

$-10000000 \leq A_i \leq 10000000$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

If we replace 3 with its square 9, then the maximum sum of all subarrays will be 9. In this scenario, array will be {9, -4, 2} and the possible subarrays are : {9}, {-4}, {2}, {9, -4}, {-4, 2}, {9, -4, 2}. So {9} subarray has the maximum sum.
If we replace -4 with its square 16, then the maximum sum will be 21 (subarray:{3, 16, 2}).
If we replace 2 with its square 4, then the maximum sum will be 4 (subarray:{4}).