Formal Proof on why Greedy isn't working on one Particular Problem

Question

Problem

You are given two integer arrays nums and multipliers of size n and m respectively, where n≥m. The arrays are 1-indexed.

You begin with a score of 0. You want to perform exactly m operations. On the iᵗʰ operation (1-indexed), you will:

• Choose one integer x from either the start or the end of the array nums.
• Add multipliers[i] * x to your score.
• Remove x from the array nums.

Return the maximum score after performing m operations.

---

Example 1

Input: nums = [1,2,3], multipliers = [3,2,1]
Output: 14

Explanation: An optimal solution is as follows:

• Choose from the end, [1,2,3], adding 3*3 = 9 to the score.
• Choose from the end, [1,2], adding 2*2 = 4 to the score.
• Choose from the end, [1], adding 1*1 = 1 to the score.

The total score is 9+4+1 = 14

Example 2

Input: nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output: 102

Explanation: An optimal solution is as follows:

• Choose from the start, [-5,-3,-3,-2,7,1], adding -5 * -10 = 50 to the score.
• Choose from the start, [-3,-3,-2,7,1], adding -3 * -5 = 15 to the score.
• Choose from the start, [-3,-2,7,1], adding -3 * 3 = -9 to the score.
• Choose from the end , [-2,7,1], adding 1 * 4 = 4 to the score.
• Choose from the end , [-2,7], adding 7 * 6 = 42 to the score.

The total score is 50 + 15 - 9 + 4 + 42 = 102.

---

My Approach

I tried to solve it using Dynamic Programming and formed following Bellman Equation.

$X[i][j]$ stores the maximum possible score after we have done $i$ total operations and used $j$ numbers from the left/start side. The index of the rightmost element can be calculated from $n-1-(i-j)$. For purpose of formulation multipliers has been renamed to $M$ while nums to $N$ $$ X[i][j] = \begin{cases} \text{max}\bigg((M[i]\cdot N[j]) + X[i+1][j+1],\\\quad\quad\quad(M[i]\cdot N[n-1-(i-j)]) + X[i+1][j]\bigg), & \text{if $i \neq m$ } \\[2ex] 0, & \text{if $i=m$} \end{cases} $$

We essentially choose the maximum on choosing from left or right. If we choose left, next operation will occur at $[i+1][j+1]$, else next operation will occur at $[i+1][j]$.

On writing code for the same, the approach worked fine 👍🏻

---

Question

Why Greedy Approach is failing here? On Going Greedy in Example 2,

• [-5,-3,-3,-2,7,1], from 50 vs -10, choose 50, hence left
• [-3,-3,-2,7,1], from 15 vs -5, choose 15, hence left
• [-3,-2,7,1], from -9 vs 3, choose 3, hence right
• [-3,-2,7], from -12 vs 28, choose 28, hence right
• [-3,-2], from -18 vs -12, choose -12, hence right

The total score is 50 + 15 + 3 + 28 - 12 = 84, which isn't optimal.

Is there a formal proof using eXchange Argument [Although the link suggests that To show that an algorithm A does not solve a problem it is sufficient to exhibit one input on which A does not produce an acceptable output] or Greedy Stays Ahead Approach$\color{red}{?}$

Any hint would be of great help. Thanks!

---

Answer 1

To prove that the greedy algorithm is not optimal, it suffices to give one counterexample, i.e. one problem instance $nums$ and $mult$ such that it is possible to obtain a value that is larger than the output computed by the greedy algorithm. You have already shown this. In fact, you showed more than that - you computed the optimal value for this problem instance, which is not necessary - it would have sufficed to show that the greedy algorithm’s output is $84$ and that there exists a sequence of decisions that gives a value larger than $84$, such as $90$, say. It’s not necessary to compute the optimal value $102$ to prove suboptimality of the greedy algorithm.

If you want to understand why the greedy algorithm is not optimal, it helps to find the smallest possible counterexamples. Suppose $nums=[5,4]$ and $mult=[1,2]$. Then, the greedy algorithm would choose to multiply the $1$ by a $5$ rather than $4$, giving an output of $1 \cdot 5+2 \cdot 4=13$. But the second multiplier $2$ is larger than the first multiplier and so should have been multiplied with the larger number $5$ to get the maximum output (which is $1 \cdot 4+2 \cdot5=14$). We can see why being greedy is suboptimal in general.