Four Weights, Best Pick

Medium

You get an array weights of exactly four integers and an integer array values of length at least four. Pick four elements of values at indices i0 < i1 < i2 < i3 and multiply them in order by the weights; the score is weights[0]·values[i0] + weights[1]·values[i1] + weights[2]·values[i2] + weights[3]·values[i3]. Return the highest score possible. Numbers can be negative, so the answer can be negative too.

Example 1

weights=[2, -1, 3, 1], values=[4, -2, 1, 5, -3, 2] → 27

Take the elements at indices 0, 1, 3 and 5: 2·4 + (-1)·(-2) + 3·5 + 1·2 = 27.

Example 2

weights=[1, 1, 1, 1], values=[-5, -1, -2, -3, -4] → -10

All values are negative and exactly four must be taken. Skipping -5 is best: -1 - 2 - 3 - 4 = -10.

Example 3

weights=[0, 3, 0, -2], values=[7, 6, 1, 8] → 2

Constraints

len(weights) = 4
4 ≤ len(values) ≤ 10⁵
-10⁵ ≤ weights[i], values[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

weights=[2, -1, 3, 1], values=[4, -2, 1, 5, -3, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 100 tests on the server, hidden ones included.