Maximum Profit Selling from Either End

Problem You are given an array P of prices of N objects, where P[i] is the price of the i-th object. You must sell every object, one per day. On each sale you may take the next object from either the left end or the right end of the remaining array. Selling an object on day k (1-indexed) earns k * price. Find the maximum total profit.

Input / Output

• Input: integer N and array P of non-negative prices.
• Output: the maximum achievable total profit.

Constraints

• N up to ~10^3 so an O(N^2) DP passes comfortably.
• Prices are non-negative integers.
• Exactly one object is sold per day, so the last object always sells on day N.

Example

• P = [1, 2, 3] → 14. Sell left (1) on day 1, left (2) on day 2, then 3 on day 3: 1·1 + 2·2 + 3·3 = 14. Taking the 3 first is worse: 1·3 + 2·1 + 3·2 = 11.
• Tricky case: greedily taking the cheaper end each day is NOT optimal — the goal is to defer expensive objects to high-multiplier late days, sometimes burning an early day on a mid-priced object.