Array
Dynamic Programming
Description
You are given two 0-indexed integer arrays nums
and multipliers
of size n
and m
respectively, where n >= m
.
You begin with a score of 0
. You want to perform exactly m
operations. On the ith
operation (0-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.
Note that multipliers[0]
corresponds to the first operation, multipliers[1]
to the second operation, and so on.
Remove x
from 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.
Constraints:
n == nums.length
m == multipliers.length
1 <= m <= 300
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def maximumScore ( self , nums : List [ int ], multipliers : List [ int ]) -> int :
@cache
def f ( i , j , k ):
if k >= m or i >= n or j < 0 :
return 0
a = f ( i + 1 , j , k + 1 ) + nums [ i ] * multipliers [ k ]
b = f ( i , j - 1 , k + 1 ) + nums [ j ] * multipliers [ k ]
return max ( a , b )
n = len ( nums )
m = len ( multipliers )
return f ( 0 , n - 1 , 0 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
private Integer [][] f ;
private int [] multipliers ;
private int [] nums ;
private int n ;
private int m ;
public int maximumScore ( int [] nums , int [] multipliers ) {
n = nums . length ;
m = multipliers . length ;
f = new Integer [ m ][ m ] ;
this . nums = nums ;
this . multipliers = multipliers ;
return dfs ( 0 , 0 );
}
private int dfs ( int i , int j ) {
if ( i >= m || j >= m || ( i + j ) >= m ) {
return 0 ;
}
if ( f [ i ][ j ] != null ) {
return f [ i ][ j ] ;
}
int k = i + j ;
int a = dfs ( i + 1 , j ) + nums [ i ] * multipliers [ k ] ;
int b = dfs ( i , j + 1 ) + nums [ n - 1 - j ] * multipliers [ k ] ;
f [ i ][ j ] = Math . max ( a , b );
return f [ i ][ j ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution {
public :
int maximumScore ( vector < int >& nums , vector < int >& multipliers ) {
int n = nums . size (), m = multipliers . size ();
int f [ m ][ m ];
memset ( f , 0x3f , sizeof f );
function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int {
if ( i >= m || j >= m || ( i + j ) >= m ) return 0 ;
if ( f [ i ][ j ] != 0x3f3f3f3f ) return f [ i ][ j ];
int k = i + j ;
int a = dfs ( i + 1 , j ) + nums [ i ] * multipliers [ k ];
int b = dfs ( i , j + 1 ) + nums [ n - j - 1 ] * multipliers [ k ];
return f [ i ][ j ] = max ( a , b );
};
return dfs ( 0 , 0 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 func maximumScore ( nums [] int , multipliers [] int ) int {
n , m := len ( nums ), len ( multipliers )
f := make ([][] int , m )
for i := range f {
f [ i ] = make ([] int , m )
for j := range f [ i ] {
f [ i ][ j ] = 1 << 30
}
}
var dfs func ( i , j int ) int
dfs = func ( i , j int ) int {
if i >= m || j >= m || i + j >= m {
return 0
}
if f [ i ][ j ] != 1 << 30 {
return f [ i ][ j ]
}
k := i + j
a := dfs ( i + 1 , j ) + nums [ i ] * multipliers [ k ]
b := dfs ( i , j + 1 ) + nums [ n - j - 1 ] * multipliers [ k ]
f [ i ][ j ] = max ( a , b )
return f [ i ][ j ]
}
return dfs ( 0 , 0 )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 function maximumScore ( nums : number [], multipliers : number []) : number {
const inf = 1 << 30 ;
const n = nums . length ;
const m = multipliers . length ;
const f = new Array ( m + 1 ). fill ( 0 ). map (() => new Array ( m + 1 ). fill ( - inf ));
f [ 0 ][ 0 ] = 0 ;
let ans = - inf ;
for ( let i = 0 ; i <= m ; ++ i ) {
for ( let j = 0 ; j <= m - i ; ++ j ) {
const k = i + j - 1 ;
if ( i > 0 ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i - 1 ][ j ] + nums [ i - 1 ] * multipliers [ k ]);
}
if ( j > 0 ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ], f [ i ][ j - 1 ] + nums [ n - j ] * multipliers [ k ]);
}
if ( i + j === m ) {
ans = Math . max ( ans , f [ i ][ j ]);
}
}
}
return ans ;
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def maximumScore ( self , nums : List [ int ], multipliers : List [ int ]) -> int :
n , m = len ( nums ), len ( multipliers )
f = [[ - inf ] * ( m + 1 ) for _ in range ( m + 1 )]
f [ 0 ][ 0 ] = 0
ans = - inf
for i in range ( m + 1 ):
for j in range ( m - i + 1 ):
k = i + j - 1
if i > 0 :
f [ i ][ j ] = max ( f [ i ][ j ], f [ i - 1 ][ j ] + multipliers [ k ] * nums [ i - 1 ])
if j > 0 :
f [ i ][ j ] = max ( f [ i ][ j ], f [ i ][ j - 1 ] + multipliers [ k ] * nums [ n - j ])
if i + j == m :
ans = max ( ans , f [ i ][ j ])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution {
public int maximumScore ( int [] nums , int [] multipliers ) {
final int inf = 1 << 30 ;
int n = nums . length , m = multipliers . length ;
int [][] f = new int [ m + 1 ][ m + 1 ] ;
for ( int i = 0 ; i <= m ; i ++ ) {
Arrays . fill ( f [ i ] , - inf );
}
f [ 0 ][ 0 ] = 0 ;
int ans = - inf ;
for ( int i = 0 ; i <= m ; ++ i ) {
for ( int j = 0 ; j <= m - i ; ++ j ) {
int k = i + j - 1 ;
if ( i > 0 ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ] , f [ i - 1 ][ j ] + multipliers [ k ] * nums [ i - 1 ] );
}
if ( j > 0 ) {
f [ i ][ j ] = Math . max ( f [ i ][ j ] , f [ i ][ j - 1 ] + multipliers [ k ] * nums [ n - j ] );
}
if ( i + j == m ) {
ans = Math . max ( ans , f [ i ][ j ] );
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
int maximumScore ( vector < int >& nums , vector < int >& multipliers ) {
const int inf = 1 << 30 ;
int n = nums . size (), m = multipliers . size ();
vector < vector < int >> f ( m + 1 , vector < int > ( m + 1 , - inf ));
f [ 0 ][ 0 ] = 0 ;
int ans = - inf ;
for ( int i = 0 ; i <= m ; ++ i ) {
for ( int j = 0 ; j <= m - i ; ++ j ) {
int k = i + j - 1 ;
if ( i > 0 ) {
f [ i ][ j ] = max ( f [ i ][ j ], f [ i - 1 ][ j ] + multipliers [ k ] * nums [ i - 1 ]);
}
if ( j > 0 ) {
f [ i ][ j ] = max ( f [ i ][ j ], f [ i ][ j - 1 ] + multipliers [ k ] * nums [ n - j ]);
}
if ( i + j == m ) {
ans = max ( ans , f [ i ][ j ]);
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 func maximumScore ( nums [] int , multipliers [] int ) int {
const inf int = 1 << 30
n , m := len ( nums ), len ( multipliers )
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , m + 1 )
for j := range f {
f [ i ][ j ] = - inf
}
}
f [ 0 ][ 0 ] = 0
ans := - inf
for i := 0 ; i <= m ; i ++ {
for j := 0 ; j <= m - i ; j ++ {
k := i + j - 1
if i > 0 {
f [ i ][ j ] = max ( f [ i ][ j ], f [ i - 1 ][ j ] + multipliers [ k ] * nums [ i - 1 ])
}
if j > 0 {
f [ i ][ j ] = max ( f [ i ][ j ], f [ i ][ j - 1 ] + multipliers [ k ] * nums [ n - j ])
}
if i + j == m {
ans = max ( ans , f [ i ][ j ])
}
}
}
return ans
}
GitHub