Given two arrays a[] and b[][2] with both having size N. N operations have to be performed, and initially counter will be 0. Additionally, there is a M bonus score for a hitting streak of b[i][0] and the bonus score received will be b[i][1], the task is to find the maximum score by performing either of the below operations optimally for all i from 1 to N.
- Operation 1: increases the counter’s value by 1 and receives a[i] score
- Operation 2: resets the counter’s value to 0, without receiving any score.
Examples:
Input: a[] = {2, 7, 1, 8, 2, 8}, b[][2] = {{2, 10}, {3, 1}, {5, 5}}
Output: 48
Explanation:
- For i = 1, Change the counter’s value from 0 to 1 and receive a 2 score.
- For i = 2, Change the counter’s value from 1 to 2 and receive a 7 score and get 10 scores as a streak bonus as well.
- For i = 3, Change the counter’s value from 2 to 0.
- For i = 4, Change the counter’s value from 0 to 1 and receive 8 scores.
- For i = 5, Change the counter’s value from 1 to 2 and receive 2 scores and get a 10 score as a streak bonus.
- For i = 6, Change the counter’s value from 2 to 3 and receive 8 scores. and get 1 score as a streak bonus.
Total score : 2 + 7 + 10 + 8 + 2 +10 + 8 +1 = 48.
Input: a[] = {1000000000, 1000000000, 1000000000}, b[][2] = {{1, 1000000000}, {3, 1000000000}}
Output: 5000000000
Naive approach: The problem can be solved based on The basis of the following idea:
Basic way to solve this problem is to generate all 2N combinations by recursive brute force.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming along with hashing can be used to solve to this problem.
- dp[i][j] represents maximum score till i’th operation with current counter j.
- recurrence relation: dp[i][j] = max(dp[i – 1][j + 1] + a[i] + hash[j + 1], dp[i – 1][0])
It can be observed that there are N * N states but the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of states. This can be done using recursive structure intact and just store the value in a HashMap and whenever the function is called, return the value store without computing .
Follow the steps below to solve the problem:
- Creating a hashmap array for mapping values of b[i][0] to b[i][1] named hash[].
- Create a recursive function that takes two parameters i representing i’th operation and j representing counter at i’th operation.
- Call the recursive function for both increasing the current counter by 1 and resetting the counter.
- Check the base case if all N operations are over then return 0.
- Create a 2d array of dp[5001][5001] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j].
- If the answer for a particular state is already computed then just return dp[i][j].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// To avoid integer overflow#define int long long// dp table initialized with - 1int dp[5001][5001];// Recursive function to count maximum score// by performing following operationsint recur(int i, int j, int a[], int hash[], int N){ // Base case if (i == N) { return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Calling recursive function for // performing operation 1 int ans = recur(i + 1, j + 1, a, hash, N) + a[i] + hash[j + 1]; // Calling recursive function for // performing operation 2 ans = max(ans, recur(i + 1, 0, a, hash, N) + 0LL); // Save and return dp value return dp[i][j] = ans;}// Function to count maximum score// by performing following operationsvoid findMaximumScore(int a[], int b[][2], int N, int M){ // Filling dp table with -1 memset(dp, -1, sizeof(dp)); // Creating Hash table int hash[N + 1] = { 0 }; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } cout << recur(0, 0, a, hash, N) << endl;}// Driver Codeint32_t main(){ // Input 1 int a[] = { 2, 7, 1, 8, 2, 8 }, b[][2] = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = sizeof(a) / sizeof(a[0]); int M = sizeof(b) / sizeof(b[0]); // Function Call findMaximumScore(a, b, N, M); // Input 2 int a1[] = { 1000000000, 1000000000, 1000000000 }, b1[][2] = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = sizeof(a1) / sizeof(a1[0]); int M1 = sizeof(b1) / sizeof(b1[0]); // Function Call findMaximumScore(a1, b1, N1, M1); return 0;} |
Java
// Java code for the above approachimport java.util.Arrays;class Main { // To avoid integer overflow static long MAX = 1000000007; // dp table initialized with - 1 static long[][] dp = new long[5001][5001]; // Recursive function to count maximum score // by performing following operations static long recur(int i, int j, int[] a, int[] hash, int N) { // Base case if (i == N) { return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) { return dp[i][j]; } // Calling recursive function for // performing operation 1 long ans = recur(i + 1, j + 1, a, hash, N) + a[i] + hash[j + 1]; // Calling recursive function for // performing operation 2 ans = Math.max(ans, recur(i + 1, 0, a, hash, N) + 0); // Save and return dp value return dp[i][j] = ans; } // Function to count maximum score // by performing following operations static void findMaximumScore(int[] a, int[][] b, int N, int M) { // Filling dp table with -1 for (long[] row : dp) { Arrays.fill(row, -1); } // Creating Hash table int[] hash = new int[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } System.out.println(recur(0, 0, a, hash, N)); } // Driver Code public static void main(String[] args) { // Input 1 int[] a = { 2, 7, 1, 8, 2, 8 }; int[][] b = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = a.length; int M = b.length; // Function Call findMaximumScore(a, b, N, M); // Input 2 int[] a1 = { 1000000000, 1000000000, 1000000000 }; int[][] b1 = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = a1.length; int M1 = b1.length; // Function Call findMaximumScore(a1, b1, N1, M1); }}// This code is contributed by Potta Lokesh |
Python3
#Python code to implement the approach# dp table initialized with - 1dp=[[-1 for i in range(5001)] for j in range(5001)]# Recursive function to count maximum score# by performing following operationsdef recur(i,j,a,hash,N): # Base case if(i==N): return 0 # If answer for current state is already # calculated then just return dp[i][j] if(dp[i][j]!=-1): return dp[i][j] # Calling recursive function for # performing operation 1 ans=recur(i+1,j+1,a,hash,N)+a[i]+hash[j+1] # Calling recursive function for # performing operation 2 ans=max(ans,recur(i+1,0,a,hash,N)) # Save and return dp value dp[i][j]=ans return dp[i][j]# Function to count maximum score# by performing following operationsdef findMaximumScore(a,b,N,M): # Filling dp table with -1 for i in range(len(dp)): for j in range(len(dp[0])): dp[i][j]=-1 # Creating Hash table hash=[0]*(N+1) # Mapping hash table with values for i in range(M): hash[b[i][0]]+=b[i][1] print(recur(0,0,a,hash,N)) # Driver Code# Input 1a=[2, 7, 1, 8, 2, 8]b=[[2,10],[3,1],[5,5]]N=len(a)M=len(b)# Function callfindMaximumScore(a,b,N,M)# Input 2a1=[1000000000, 1000000000, 1000000000]b1=[[1,1000000000],[3,1000000000]]N1=len(a1)M1=len(b1)# Function callfindMaximumScore(a1,b1,N1,M1)# This code is contributed by Pushpesh Raj. |
C#
using System;using System.Linq;class GFG{ // To avoid integer overflow static long MAX = 1000000007; // dp table initialized with - 1 static long[, ] dp = new long[5001, 5001]; // Recursive function to count maximum score // by performing following operations static long recur(int i, int j, int[] a, int[] hash, int N) { // Base case if (i == N) { return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i, j] != -1) { return dp[i, j]; } // Calling recursive function for // performing operation 1 long ans = recur(i + 1, j + 1, a, hash, N) + a[i] + hash[j + 1]; // Calling recursive function for // performing operation 2 ans = Math.Max(ans, recur(i + 1, 0, a, hash, N) + 0); // Save and return dp value return dp[i, j] = ans; } // Function to count maximum score // by performing following operations static void findMaximumScore(int[] a, int[, ] b, int N, int M) { // Filling dp table with -1 for (int i = 0; i < 5001; i++) { for (int j = 0; j < 5001; j++) { dp[i, j] = -1; } } // Creating Hash table int[] hash = new int[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i, 0]] += b[i, 1]; } Console.WriteLine(recur(0, 0, a, hash, N)); } // Driver Code public static void Main(string[] args) { // Input 1 int[] a = { 2, 7, 1, 8, 2, 8 }; int[, ] b = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = a.Length; int M = b.GetLength(0); // Function Call findMaximumScore(a, b, N, M); // Input 2 int[] a1 = { 1000000000, 1000000000, 1000000000 }; int[, ] b1 = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = a1.Length; int M1 = b1.GetLength(0); // Function Call findMaximumScore(a1, b1, N1, M1); }}// This code is contributed by ik_9 |
Javascript
// Javascript code to implement the approach// dp table initialized with - 1let dp=new Array(5001);for(let i=0; i<5001; i++) dp[i]=new Array(5001);// Recursive function to count maximum score// by performing following operationsfunction recur(i, j, a, hash, N){ // Base case if (i == N) { return 0; } // If answer for current state is already // calculated then just return dp[i][j] if (dp[i][j] != -1) return dp[i][j]; // Calling recursive function for // performing operation 1 let ans = recur(i + 1, j + 1, a, hash, N) + a[i] + hash[j + 1]; // Calling recursive function for // performing operation 2 ans = Math.max(ans, recur(i + 1, 0, a, hash, N) + 0); // Save and return dp value return dp[i][j] = ans;}// Function to count maximum score// by performing following operationsfunction findMaximumScore(a, b, N, M){ // Filling dp table with -1 for(let i=0; i<5001; i++) for(let j=0; j<5001; j++) dp[i][j]=-1; // Creating Hash table let hash = new Array(N+1).fill(0); // Mapping hash table with values for (let i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } document.write(recur(0, 0, a, hash, N))}// Driver Code // Input 1 let a = [ 2, 7, 1, 8, 2, 8 ], b = [[ 2, 10 ], [ 3, 1 ], [ 5, 5 ]]; let N = a.length; let M = b.length; // Function Call findMaximumScore(a, b, N, M); document.write("<br>"); // Input 2 let a1 = [ 1000000000, 1000000000, 1000000000 ], b1 = [ [ 1, 1000000000 ], [ 3, 1000000000 ] ]; let N1 = a1.length; let M1 = b1.length; // Function Call findMaximumScore(a1, b1, N1, M1); |
Output
48 5000000000
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// To avoid integer overflow#define int long long// dp tableint dp[5001][5001];// Function to count maximum score// by performing following operationsvoid findMaximumScore(int a[], int b[][2], int N, int M){ // Creating Hash table int hash[N + 1] = { 0 }; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // Base case initialization for (int i = 0; i <= N; i++) { dp[N][i] = 0; } // Tabulation for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // Operation 1 int ans = dp[i + 1][j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = max(ans, dp[i + 1][0]); dp[i][j] = ans; } } cout << dp[0][0] << endl;}// Driver Codeint32_t main(){ // Input 1 int a[] = { 2, 7, 1, 8, 2, 8 }, b[][2] = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = sizeof(a) / sizeof(a[0]); int M = sizeof(b) / sizeof(b[0]); // Function Call findMaximumScore(a, b, N, M); // Input 2 int a1[] = { 1000000000, 1000000000, 1000000000 }, b1[][2] = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = sizeof(a1) / sizeof(a1[0]); int M1 = sizeof(b1) / sizeof(b1[0]); // Function Call findMaximumScore(a1, b1, N1, M1); return 0;} |
Java
import java.util.Arrays;public class MaximumScore { // Function to count maximum score static void findMaximumScore(int[] a, int[][] b, int N, int M) { // To avoid integer overflow long[][] dp = new long[N + 1][N + 1]; // Creating Hash table long[] hash = new long[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // Base case initialization for (int i = 0; i <= N; i++) { dp[N][i] = 0; } // Tabulation for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // Operation 1 long ans = dp[i + 1][j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = Math.max(ans, dp[i + 1][0]); dp[i][j] = ans; } } System.out.println(dp[0][0]); } public static void main(String[] args) { // Input 1 int[] a = { 2, 7, 1, 8, 2, 8 }; int[][] b = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = a.length; int M = b.length; // Function Call findMaximumScore(a, b, N, M); // Input 2 int[] a1 = { 1000000000, 1000000000, 1000000000 }; int[][] b1 = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = a1.length; int M1 = b1.length; // Function Call findMaximumScore(a1, b1, N1, M1); }} |
Python
import numpy as np# Function to count maximum score# by performing following operationsdef findMaximumScore(a, b, N, M): # Creating Hash table hash = np.zeros(N + 1) # Mapping hash table with values for i in range(M): hash[b[i][0]] += b[i][1] # Base case initialization dp = np.zeros((N + 1, N + 1)) # Tabulation for i in range(N - 1, -1, -1): for j in range(i + 1): ans = dp[i + 1][j + 1] + a[i] + hash[j + 1] ans = max(ans, dp[i + 1][0]) dp[i][j] = ans print(dp[0][0])# Input 1a = [2, 7, 1, 8, 2, 8]b = [[2, 10], [3, 1], [5, 5]]N = len(a)M = len(b)findMaximumScore(a, b, N, M)# Input 2a1 = [1000000000, 1000000000, 1000000000]b1 = [[1, 1000000000], [3, 1000000000]]N1 = len(a1)M1 = len(b1)findMaximumScore(a1, b1, N1, M1) |
C#
using System;public class GFG{ public static void FindMaximumScore(int[] a, int[][] b, int N, int M) { // Creating Hash table long[] hash = new long[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // dp table long[,] dp = new long[5001, 5001]; // Base case initialization for (int i = 0; i <= N; i++) { dp[N, i] = 0; } // Tabulation for (int i = N - 1; i >= 0; i--) { for (int j = 0; j <= i; j++) { // Operation 1 long ans = dp[i + 1, j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = Math.Max(ans, dp[i + 1, 0]); dp[i, j] = ans; } } Console.WriteLine(dp[0, 0]); } public static void Main() { // Input 1 int[] a = { 2, 7, 1, 8, 2, 8 }; int[][] b = { new int[] { 2, 10 }, new int[] { 3, 1 }, new int[] { 5, 5 } }; int N = a.Length; int M = b.Length; // Function Call FindMaximumScore(a, b, N, M); // Input 2 int[] a1 = { 1000000000, 1000000000, 1000000000 }; int[][] b1 = { new int[] { 1, 1000000000 }, new int[] { 3, 1000000000 } }; int N1 = a1.Length; int M1 = b1.Length; // Function Call FindMaximumScore(a1, b1, N1, M1); }} |
Javascript
// Function to count maximum score// by performing following operationsfunction findMaximumScore(a, b, N, M) { // Creating Hash table var hash = new Array(N + 1).fill(0); // Mapping hash table with values for (var i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // Base case initialization var dp = new Array(N + 1).fill(0).map(() => new Array(N + 1).fill(0)); // Tabulation for (var i = N - 1; i >= 0; i--) { for (var j = 0; j <= i; j++) { var ans = dp[i + 1][j + 1] + a[i] + hash[j + 1]; ans = Math.max(ans, dp[i + 1][0]); dp[i][j] = ans; } } console.log(dp[0][0]);}// Input 1 var a = [2, 7, 1, 8, 2, 8];var b = [[2, 10], [3, 1], [5, 5]];var N = a.length;var M = b.length;findMaximumScore(a, b, N, M);// Input 2var a1 = [1000000000, 1000000000, 1000000000];var b1 = [[1, 1000000000], [3, 1000000000]];var N1 = a1.length;var M1 = b1.length;findMaximumScore(a1, b1, N1, M1); |
Output
48 5000000000
Time Complexity: O(N^2)
Auxiliary Space: O(N^2)
Efficient approach : Space optimization
In previous approach the dp[i][j] is depend upon the current and previous row of 2D matrix. So to optimize space we use two vectors curr and next that keep track of current and next row of DP.
Implementation :
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// To avoid integer overflow#define int long long// Function to count maximum score// by performing following operationsvoid findMaximumScore(int a[], int b[][2], int N, int M){ // Creating Hash table int hash[N + 1] = { 0 }; // to store the values of next row of DP vector<int> next(N + 1, 0); // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // iterating over DP to get the current // value from previous computations for (int i = N - 1; i >= 0; i--) { vector<int> curr(N + 1); for (int j = 0; j <= i; j++) { // Operation 1 int ans = next[j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = max(ans, next[0]); curr[j] = ans; } // assigning values to iterate further next = curr; } // print final answer cout << next[0] << endl;}// Driver Codeint32_t main(){ // Input 1 int a[] = { 2, 7, 1, 8, 2, 8 }, b[][2] = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = sizeof(a) / sizeof(a[0]); int M = sizeof(b) / sizeof(b[0]); // Function Call findMaximumScore(a, b, N, M); // Input 2 int a1[] = { 1000000000, 1000000000, 1000000000 }, b1[][2] = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = sizeof(a1) / sizeof(a1[0]); int M1 = sizeof(b1) / sizeof(b1[0]); // Function Call findMaximumScore(a1, b1, N1, M1); return 0;} |
Java
import java.util.Arrays;public class Main { // Function to count maximum score // by performing following operations static void findMaximumScore(long a[], long b[][], int N, int M) { // Creating Hash table long hash[] = new long[N + 1]; // to store the values of the next row of DP long[] next = new long[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[(int)b[i][0]] += b[i][1]; } // iterating over DP to get the current // value from previous computations for (int i = N - 1; i >= 0; i--) { long[] curr = new long[N + 1]; for (int j = 0; j <= i; j++) { // Operation 1 long ans = next[j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = Math.max(ans, next[0]); curr[j] = ans; } // assigning values to iterate further next = Arrays.copyOf(curr, curr.length); } // print final answer System.out.println(next[0]); } // Driver Code public static void main(String[] args) { // Input 1 long a[] = { 2, 7, 1, 8, 2, 8 }; long b[][] = { { 2, 10 }, { 3, 1 }, { 5, 5 } }; int N = a.length; int M = b.length; // Function Call findMaximumScore(a, b, N, M); // Input 2 long a1[] = { 1000000000, 1000000000, 1000000000 }; long b1[][] = { { 1, 1000000000 }, { 3, 1000000000 } }; int N1 = a1.length; int M1 = b1.length; // Function Call findMaximumScore(a1, b1, N1, M1); }} |
Python3
# Python code for the above approach# Function to count maximum score# by performing following operationsdef findMaximumScore(a, b, N, M): # Creating Hash table hash = [0] * (N + 1) # to store the values of the next row of DP next_row = [0] * (N + 1) # Mapping hash table with values for i in range(M): hash[b[i][0]] += b[i][1] # iterating over DP to get the current # value from previous computations for i in range(N - 1, -1, -1): curr = [0] * (N + 1) for j in range(i + 1): # Operation 1 ans = next_row[j + 1] + a[i] + hash[j + 1] # Operation 2 ans = max(ans, next_row[0]) curr[j] = ans # assigning values to iterate further next_row = curr # print final answer print(next_row[0])# Driver Code# Input 1a = [2, 7, 1, 8, 2, 8]b = [[2, 10], [3, 1], [5, 5]]N = len(a)M = len(b)# Function CallfindMaximumScore(a, b, N, M)# Input 2a1 = [1000000000, 1000000000, 1000000000]b1 = [[1, 1000000000], [3, 1000000000]]N1 = len(a1)M1 = len(b1)# Function CallfindMaximumScore(a1, b1, N1, M1)# This code is contributed by Vaibhav Nandan |
C#
using System;public class GFG { // Function to count maximum score // by performing the following operations public static void FindMaximumScore(long[] a, long[][] b, int N, int M) { // Creating a hash table long[] hash = new long[N + 1]; // To store the values of the next row of DP long[] next = new long[N + 1]; // Mapping hash table with values for (int i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // Iterating over DP to get the current // value from previous computations for (int i = N - 1; i >= 0; i--) { long[] curr = new long[N + 1]; for (int j = 0; j <= i; j++) { // Operation 1 long ans = next[j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = Math.Max(ans, next[0]); curr[j] = ans; } // Assigning values to iterate further next = curr; } // Print the final answer Console.WriteLine(next[0]); } // Driver Code public static void Main() { // Input 1 long[] a = { 2, 7, 1, 8, 2, 8 }; long[][] b = { new long[] { 2, 10 }, new long[] { 3, 1 }, new long[] { 5, 5 } }; int N = a.Length; int M = b.Length; // Function Call FindMaximumScore(a, b, N, M); // Input 2 long[] a1 = { 1000000000, 1000000000, 1000000000 }; long[][] b1 = { new long[] { 1, 1000000000 }, new long[] { 3, 1000000000 } }; int N1 = a1.Length; int M1 = b1.Length; // Function Call FindMaximumScore(a1, b1, N1, M1); }} |
Javascript
// JS code for the above approach// Function to count maximum score// by performing following operationsfunction findMaximumScore(a, b, N, M){ // Creating Hash table let hash = new Array(N + 1).fill(0); // to store the values of next row of DP let next = new Array(N + 1).fill(0); // Mapping hash table with values for (let i = 0; i < M; i++) { hash[b[i][0]] += b[i][1]; } // iterating over DP to get the current // value from previous computations for (let i = N - 1; i >= 0; i--) { let curr = new Array(N + 1); for (let j = 0; j <= i; j++) { // Operation 1 let ans = next[j + 1] + a[i] + hash[j + 1]; // Operation 2 ans = Math.max(ans, next[0]); curr[j] = ans; } // assigning values to iterate further next = curr; } // print final answer console.log(next[0]);}// Driver Code// Input 1let a = [ 2, 7, 1, 8, 2, 8 ];let b = [ [ 2, 10 ], [ 3, 1 ], [ 5, 5 ] ];let N = a.length;let M = b.length;// Function CallfindMaximumScore(a, b, N, M);// Input 2let a1 = [ 1000000000, 1000000000, 1000000000 ];let b1 = [ [ 1, 1000000000 ], [ 3, 1000000000 ] ];let N1 = a1.length;let M1 = b1.length;// Function CallfindMaximumScore(a1, b1, N1, M1); |
Output
48 5000000000
Time Complexity: O(N^2)
Auxiliary Space: O(N)
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
- Introduction to Hashing – Data Structures and Algorithms Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
