1
$\begingroup$

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!


$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ May 13 at 21:21
  • 2
    $\begingroup$ You have given a formal proof by showing a counterexample. A single counterexample is a full, complete, totally formal proof. $\endgroup$
    – John L.
    May 13 at 21:22
  • $\begingroup$ 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?" $\endgroup$
    – John L.
    May 13 at 21:29
  • 1
    $\begingroup$ (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.) $\endgroup$
    – John L.
    May 13 at 21:39
  • $\begingroup$ "Why Greedy Approach is failing here?" - because a greedy algorithm does not account for much enough data. $\endgroup$
    – rus9384
    May 14 at 9:04

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.