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

## 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, , 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!

• To show that the greedy approach fails, all you have to do is come up with a counterexample. No further proof is needed. Exchange arguments are used to prove that greedy approaches work, and are irrelevant here. May 13 at 21:21
• You have given a formal proof by showing a counterexample. A single counterexample is a full, complete, totally formal proof. May 13 at 21:22
• What you wanted to ask might have been "how can I understand why greedy approach fails for this problem?" or "Why is 'exchange argument/greedy stays ahead' not applicable to this greedy algorithm?" May 13 at 21:29
• (About your style of formatting: all people around here that I know well do not prefer/use a lot of decorations such as boldfaces, italics, quotation marks for non-quotations, many headers. It reads to me like someone who wants to startle me or someone who do not think I am capable of reading or who is not sure of their statements. Of course, you are free to choose your style.) May 13 at 21:39
• "Why Greedy Approach is failing here?" - because a greedy algorithm does not account for much enough data. May 14 at 9:04

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.