hardDynamic Programming 2DPure DSA~35 min
Maximum Score from Sequenced Multipliers
You apply a fixed list of weight multipliers one per round. Each round you consume either the leftmost or rightmost value from a row of metrics, scoring multiplier times that value. Maximize the total.
Problem
Given arrays nums and multipliers, perform m = multipliers.length operations. In the i-th operation (0-indexed) pick either the first or last remaining element x of nums and add multipliers[i] * x to your score, then remove x. Return the maximum possible score.
Input
An integer array nums and an integer array multipliers with multipliers.length <= nums.length.
Output
An integer: the maximum achievable score.
Constraints
- 1 <= multipliers.length <= 300
- multipliers.length <= nums.length <= 100000
- -1000 <= nums[i], multipliers[i] <= 1000
Examples
Example 1
Input
nums = [1,2,3], multipliers = [3,2,1]
Output
14
Take 3*3, 2*2, 1*1 = 9+4+1 = 14.
Example 2
Input
nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
Output
102
An optimal sequence of end choices yields 102.