Given an array arr[] of size N, with values either 1, 2, or 3. Traverse the array from left to right and before traversal predict one number from 1, 2, or 3, if arr[i] is matched with the prediction score will be increased by 1. The prediction can be switched at most K times. Find the maximum score possible.
Examples:
Input: A[] = {1, 1, 2, 1, 3}, K = 1
Output: 4
Explanation:
Following is the optimal way to perform the above operations:
Initially choose P = 1 for the i = 0 as number matches with A[0] = 1, received 1 point.
For i = 1, A[1] = 1 and we did not change chosen number P = 1 , as A[1] and P are equal we received another 1 point.
For i = 2, A[2] = 2 and we did not change chosen number P = 1 so, we do not receive point since P != A[2].
For i = 3, A[3] = 1 and we did not change chosen number P = 1 so, we receives another one point since P = A[3].
For i = 4, A[4] = 3 and we switch P to 3 since we can make a switch at most K = 1 times. P = 3 and A[4] is also 3 so we receive another point.
With this strategy, we receive a total of 4 points.Input: A[] = {3, 3, 1, 3, 3, 2, 2, 2 }, K = 0
Output: 4
Explanation: It is optimal to choose 3 for all indices since we cannot make changes once we select a particular number because K = 0.
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to explore all possible combinations by using a recursive approach.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem.
dp[i][j][k] represents the maximum score till ith element with j chosen in the last match along with k switches left.
Recurrence relation is one of the following depending upon the value of K and we are switching to which number:
- dp[i][j]k] = max(dp[i + 1][1][k] + (A[i] == 1), dp[i + 1][2][k – 1] + (A[i] == 2), dp[i + 1][3][k – 1] + (A[i] == 3))
- dp[i][j]k] = max(dp[i + 1][1][k – 1] + (A[i] == 1), dp[i + 1][2][k] + (A[i] == 2), dp[i + 1][3][k – 1] + (A[i] == 3))
- dp[i][j]k] = max(dp[i + 1][1][k – 1] + (A[i] == 1), dp[i + 1][2][k – 1] + (A[i] == 2), dp[i + 1][3][k] + (A[i] == 3))
It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state.
Follow the steps below to solve the problem:
- Create a 3d array of dp[N][5][21] initially filled with -1.
- Create a recursive function that takes three parameters i representing ith element,, j representing the last element chosen, and k representing the number of switches left.
- Check the base case, if all matches over return 0.
- If the answer for a particular state is computed then save it in dp[i][j][k].
- Otherwise, call the recursive function three times for choosing all three numbers.
- If the answer for a particular state is already computed then just return dp[i][j][k].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp table initializationint dp[100001][5][21];// Recursive function to calculate maximum// score from traversing left to right.int recur(int i, int j, int k, int A[], 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][k] != -1) return dp[i][j + 1][k]; int ans = INT_MIN; // Calling recursive function for choosing 1 if ((k != 0) or (k == 0 and j == 1)) ans = max( ans, recur(i + 1, 1, (j == 1) ? k : k - 1, A, N) + (A[i] == 1)); // Calling recursive function for choosing 2 if ((k != 0) or (k == 0 and j == 2)) ans = max( ans, recur(i + 1, 2, (j == 2) ? k : k - 1, A, N) + (A[i] == 2)); // Calling recursive function for choosing 3 if ((k != 0) or (k == 0 and j == 3)) ans = max( ans, recur(i + 1, 3, (j == 3) ? k : k - 1, A, N) + (A[i] == 3)); // Save and return dp value return dp[i][j + 1][k] = ans;}// Function to calculate maximum score// by traversing left to rightint minCost(int A[], int N, int K){ // Filling dp table with -1 memset(dp, -1, sizeof(dp)); // Calling the utility function return recur(0, -1, K + 1, A, N);}// Driver Codeint main(){ // Test Case 1 int A[] = { 1, 1, 2, 1, 3 }, K = 1; int N = sizeof(A) / sizeof(A[0]); // Function Call cout << minCost(A, N, K) << endl; // Test Case 2 int A1[] = { 3, 3, 1, 3, 3, 2, 2, 2 }, K1 = 0; int N1 = sizeof(A1) / sizeof(A1[0]); // Function Call cout << minCost(A1, N1, K1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // dp table initialization static int[][][] dp = new int[100001][5][21]; // Recursive function to calculate maximum // score from traversing left to right. static int recur(int i, int j, int k, int[] A, 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][k] != -1) return dp[i][j + 1][k]; int ans = Integer.MIN_VALUE; // Calling recursive function for choosing 1 if ((k != 0) || (k == 0 && j == 1)) ans = Math.max( ans, recur(i + 1, 1, (j == 1) ? k : k - 1, A, N) + (A[i] == 1 ? 1 : 0)); // Calling recursive function for choosing 2 if ((k != 0) || (k == 0 && j == 2)) ans = Math.max( ans, recur(i + 1, 2, (j == 2) ? k : k - 1, A, N) + (A[i] == 2 ? 1 : 0)); // Calling recursive function for choosing 3 if ((k != 0) || (k == 0 && j == 3)) ans = Math.max( ans, recur(i + 1, 3, (j == 3) ? k : k - 1, A, N) + (A[i] == 3 ? 1 : 0)); // Save and return dp value return dp[i][j + 1][k] = ans; } // Function to calculate maximum score // by traversing left to right static int minCost(int[] A, int N, int K) { // Filling dp table with -1 for (int[][] dp1 : dp) { for (int[] dp11 : dp1) { Arrays.fill(dp11, -1); } } // Calling the utility function return recur(0, -1, K + 1, A, N); } public static void main(String[] args) { // Test Case 1 int[] A = { 1, 1, 2, 1, 3 }; int K = 1; int N = A.length; // Function Call System.out.println(minCost(A, N, K)); // Test Case 2 int[] A1 = { 3, 3, 1, 3, 3, 2, 2, 2 }; int K1 = 0; int N1 = A1.length; // Function Call System.out.println(minCost(A1, N1, K1)); }}// This code is contributed by lokesh. |
Python3
import sys# dp table initializationdp = [[[-1 for _ in range(21)] for _ in range(5)] for _ in range(100001)]# Recursive function to calculate maximum score from traversing left to right.def recur(i, j, k, A, 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][k] != -1: return dp[i][j + 1][k] ans = -sys.maxsize # Calling recursive function for choosing 1 if k != 0 or (k == 0 and j == 1): ans = max( ans, recur(i + 1, 1, k - 1 if j != 1 else k, A, N) + (A[i] == 1) ) # Calling recursive function for choosing 2 if k != 0 or (k == 0 and j == 2): ans = max( ans, recur(i + 1, 2, k - 1 if j != 2 else k, A, N) + (A[i] == 2) ) # Calling recursive function for choosing 3 if k != 0 or (k == 0 and j == 3): ans = max( ans, recur(i + 1, 3, k - 1 if j != 3 else k, A, N) + (A[i] == 3) ) # Save and return dp value dp[i][j + 1][k] = ans return dp[i][j + 1][k]# Function to calculate maximum score by traversing left to rightdef minCost(A, N, K): # Filling dp table with -1 global dp dp = [[[-1 for _ in range(21)] for _ in range(5)] for _ in range(N + 1)] # Calling the utility function return recur(0, -1, K + 1, A, N)# Driver Codeif __name__ == '__main__': # Test Case 1 A = [1, 1, 2, 1, 3] K = 1 N = len(A) # Function Call print(minCost(A, N, K)) # Test Case 2 A1 = [3, 3, 1, 3, 3, 2, 2, 2] K1 = 0 N1 = len(A1) # Function Call print(minCost(A1, N1, K1)) |
C#
// C# code to implement the approachusing System;public class GFG { // dp table initialization static int[, , ] dp = new int[100001, 5, 21]; // Recursive function to calculate maximum // score from traversing left to right. static int recur(int i, int j, int k, int[] A, 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, k] != -1) { return dp[i, j + 1, k]; } int ans = int.MinValue; // Calling recursive function for choosing 1 if ((k != 0) || (k == 0 && j == 1)) { ans = Math.Max( ans, recur(i + 1, 1, (j == 1) ? k : k - 1, A, N) + (A[i] == 1 ? 1 : 0)); } // Calling recursive function for choosing 2 if ((k != 0) || (k == 0 && j == 2)) { ans = Math.Max( ans, recur(i + 1, 2, (j == 2) ? k : k - 1, A, N) + (A[i] == 2 ? 1 : 0)); } // Calling recursive function for choosing 3 if ((k != 0) || (k == 0 && j == 3)) { ans = Math.Max( ans, recur(i + 1, 3, (j == 3) ? k : k - 1, A, N) + (A[i] == 3 ? 1 : 0)); } // Save and return dp value return dp[i, j + 1, k] = ans; } // Function to calculate maximum score // by traversing left to right static int minCost(int[] A, int N, int K) { // Filling dp table with -1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { for (int l = 0; l < dp.GetLength(2); l++) { dp[i, j, l] = -1; } } } // Calling the utility function return recur(0, -1, K + 1, A, N); } static public void Main() { // Code // Test Case 1 int[] A = { 1, 1, 2, 1, 3 }; int K = 1; int N = A.Length; // Function Call Console.WriteLine(minCost(A, N, K)); // Test Case 2 int[] A1 = { 3, 3, 1, 3, 3, 2, 2, 2 }; int K1 = 0; int N1 = A1.Length; // Function Call Console.WriteLine(minCost(A1, N1, K1)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approachfunction minCost(A, N, K) {// dp table initialization let dp = []; for (let i = 0; i <= N; i++) { dp[i] = []; for (let j = 0; j <= 4; j++) { dp[i][j] = []; for (let k = 0; k <= 21; k++) { dp[i][j][k] = -1; } } }// Recursive function to calculate maximum score from traversing left to right. function recur(i, j, k) { // 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][k] !== -1) { return dp[i][j + 1][k]; } let ans = Number.MIN_SAFE_INTEGER;// Calling recursive function for choosing 1 if ((k !== 0) || (k === 0 && j === 1)) { ans = Math.max( ans, recur(i + 1, 1, (j === 1) ? k : k - 1) + (A[i] === 1) ); }// Calling recursive function for choosing 2 if ((k !== 0) || (k === 0 && j === 2)) { ans = Math.max( ans, recur(i + 1, 2, (j === 2) ? k : k - 1) + (A[i] === 2) ); }// Calling recursive function for choosing 3 if ((k !== 0) || (k === 0 && j === 3)) { ans = Math.max( ans, recur(i + 1, 3, (j === 3) ? k : k - 1) + (A[i] === 3) ); } return dp[i][j + 1][k] = ans; } return recur(0, -1, K + 1);}// Test Case 1let A = [1, 1, 2, 1, 3];let K = 1;let N = A.length;// Function Callconsole.log(minCost(A, N, K));// Test Case 2let A1 = [3, 3, 1, 3, 3, 2, 2, 2];let K1 = 0;let N1 = A1.length;// Function Callconsole.log(minCost(A1, N1, K1));// code by ksam24000 |
Output
4 4
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles :
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
- Introduction to Arrays – Data Structure and Algorithm 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!
Share your thoughts in the comments
