Maximum Profit Selling from Either End of an Array (Day-Weighted)

Problem: You are given an array P of prices of N objects, where P[i] denotes the price of the i'th object. You must sell all the objects one at a time; on each sale you may pick the next object from either the left end or the right end of the remaining array. The profit earned by selling an object on day k (1-indexed) is k times the object's price. Find the maximum total profit achievable.

Constraints: 1 <= N <= throughput typical of a medium DP problem; prices can be any non-negative integers.

Example: P = [1, 2, 3] -> selling order and day multipliers must be chosen to maximize sum(day * price); trying all left/right pick sequences and taking the max.

Approach: Classic interval DP. Define dp[i][j] = max profit obtainable from the remaining subarray P[i..j], where the current day = N - (j - i + 1) + 1 is derivable from the window size. At each state choose max of taking P[i] on the current day (dp[i+1][j] + dayP[i]) or taking P[j] on the current day (dp[i][j-1] + dayP[j]). O(N^2) time, O(N^2) space (or O(N) with rolling arrays).