Company: National Payments Corporation of India
Difficulty: medium
Problem Statement In the bustling city of Techville, Alex is working on a special project that involves optimizing a list of data values. They have an array A of n integers, where n is always an odd number. Alex needs to perform a series of operations to reduce the array down to a single value. In each operation, Alex can remove two adjacent elements from the array and then combine the remaining parts. For example, given the array [1, 8, 3, 2, 9], Alex can obtain [3, 2, 9] by removing the adjacent elements [1, 8] or obtain [1, 8, 3] by removing [2, 9] but can not obtain [8, 3, 2] as 1 and 9 aren't adjacent elements. The goal is to maximize the value of the last remaining element after performing these operations. Alex needs your help to determine the maximum possible value of the last element in the array after all possible operations are performed optimally. Input Format: The input consists of two lines: The first line contains the integer n representing the size of the array A . The