# Max Multiplied Pairings Sequel - Google Top Interview Questions

### Problem Statement :

```You are given two lists of integers nums and multipliers.

For each i = 0 to i = multiplers.length - 1, inclusive, perform the following operation:

Remove one integer e from either the beginning or the end of nums
Return the maximum total possible after performing the operations.

Constraints

0 ≤ m ≤ n ≤ 1,000 where n is the length of nums and m is the length of multipliers

Example 1

Input

nums = [5, 2, -7]
multipliers = [2, 4, -1]

Output

25
Explanation

We can get 5 * 2 + 2 * 4 + -7 * -1 = 25```

### Solution :

```                        ```Solution in C++ :

int solve(vector<int>& nums, vector<int>& m) {
if (m.empty()) return 0;
if (m.size() == 1) return max(m * nums.front(), m * nums.back());
int M = nums.size(), N = m.size(), ans = INT_MIN;
vector<vector<int>> dp(N + 1, vector<int>(N + 1, INT_MIN));
dp = m * nums.front();
dp = m * nums.back();
for (int i = 2; i <= N; i++) {
for (int j = 0; j <= i; j++) {
int a = j == i ? INT_MIN : (dp[i - j - 1][j] + nums[i - j - 1] * m[i - 1]);
int b = j == 0 ? INT_MIN : (dp[i - j][j - 1] + nums[M - j] * m[i - 1]);
dp[i - j][j] = max(a, b);
if (i == N) ans = max(ans, dp[i - j][j]);
}
}
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[] nums, int[] multipliers) {
if (nums == null || nums.length == 0)
return 0;
return getMax(
nums, multipliers, 0, nums.length - 1, 0, multipliers.length - 1, new HashMap());
}

private int getMax(int[] nums, int[] mul, int low, int high, int idx, int high2,
Map<String, Integer> memo_map) {
if (idx == high2)
return Math.max(nums[low] * mul[idx], nums[high] * mul[idx]);

String str = new StringBuilder().append(low).append(high).append(idx).toString();
if (memo_map.containsKey(str))
return memo_map.get(str);

int val1 =
nums[low] * mul[idx] + getMax(nums, mul, low + 1, high, idx + 1, high2, memo_map);
int val2 =
nums[high] * mul[idx] + getMax(nums, mul, low, high - 1, idx + 1, high2, memo_map);

memo_map.put(str, Math.max(val1, val2));
return memo_map.get(str);
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, nums, mult):
n, m = len(nums), len(mult)

@functools.cache
def go(i, j):
if j == m:
return 0
return max(
nums[i] * mult[j] + go(i + 1, j + 1), nums[n - j + i - 1] * mult[j] + go(i, j + 1)
)

return go(0, 0)```
```

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your \$inOrder* func

## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F