Maximizing Ball Removal in Sequences
Given n balls arranged in a line. The color of the i-th ball from the left is ai. you can perform following operation any number of times:
- Select i and j such that 1 ≤ i < j ≤ |a| and ai = aj
- Remove ai, ai+1,…, aj from the array (and decrease the indices of all elements to the right of aj by (j−i+1).
The task is to find the maximum number of ball that can be removed.
Example:
Input: n = 5, a[] = {1, 2, 2, 3, 3}
Output: 4Input: n = 4, a[] = {1, 2, 1, 2 }
Output: 3
Approach:
Consider the problem of deleting ranges of balls to maximize the total number of remaining balls. To achieve the maximum, we need to find disjoint ranges with identical colors and maximize the sum of their lengths.
We observe that deleting ranges like (a, c) and (b, d) where a < b < c < d is not possible. Similarly, if we delete ranges (a, d) and (b, c) where a < b < c < d, we must have deleted range (b, c) before (a, d). However, the effect is the same as only deleting (a, d).
Therefore, in an optimal solution, the deleted ranges are disjoint. To maximize the sum of lengths, we aim to find disjoint ranges [l1, r1], [l2, r2], …, [lm, rm] such that ali = ari (same color), and the sum ∑(ri − li + 1) is maximized.
We can formulate this as a dynamic programming problem. Let dpi denote the minimum number of points not deleted when considering the subarray a[1…i]. We have dpi = min(dpi-1 + 1, min{dpj | aj+1 = ai, j + 1 < i}).
This dynamic programming can be efficiently calculated in O(n) since we can store, for each color x, the minimum dpj satisfying aj+1 = x.
Steps:
- Iterate over each ball from 1 to n.
- Update the dynamic programming array dp based on the recurrence relation:
- dp[i] = min(dp[i – 1] + 1, last_occurrence[a[i]])
- It represents the minimum number of points (balls) not deleted when considering the subarray a[1…i].
- Update the last_occurrence array for the current color.
- Print the result for the current test case, which is n – dp[n].
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; const int MAX_N = 200000 + 5; int main() { int n = 4; // Number of balls vector< int > tempA = { 1, 2, 1, 2 }; // Colors of the balls vector< int > a(MAX_N); vector< int > dp(MAX_N); vector< int > last_occurrence(MAX_N, INT_MAX); // Initialize arrays dp[0] = 0; // Input colors of each ball and calculate DP values for ( int i = 1; i <= n; i++) { a[i] = tempA[i - 1]; dp[i] = min(dp[i - 1] + 1, last_occurrence[a[i]]); last_occurrence[a[i]] = min(last_occurrence[a[i]], dp[i - 1]); } // Output the result for the current test case cout << n - dp[n] << '\n' ; } |
Java
import java.util.*; public class GFG { static final int MAX_N = 200000 + 5 ; public static void main(String[] args) { int n = 4 ; // Number of balls List<Integer> tempA = Arrays.asList( 1 , 2 , 1 , 2 ); // Colors of the balls List<Integer> a = new ArrayList<>(Collections.nCopies(MAX_N, 0 )); List<Integer> dp = new ArrayList<>(Collections.nCopies(MAX_N, 0 )); List<Integer> last_occurrence = new ArrayList<>(Collections.nCopies(MAX_N, Integer.MAX_VALUE)); // Initialize arrays dp.set( 0 , 0 ); // Input colors of each ball and calculate DP values for ( int i = 1 ; i <= n; i++) { a.set(i, tempA.get(i - 1 )); dp.set(i, Math.min(dp.get(i - 1 ) + 1 , last_occurrence.get(a.get(i)))); last_occurrence.set(a.get(i), Math.min(last_occurrence.get(a.get(i)), dp.get(i - 1 ))); } // Output the result for the current test case System.out.println(n - dp.get(n)); } } |
Python3
MAX_N = 200000 + 5 def main(): n = 4 # Number of balls temp_a = [ 1 , 2 , 1 , 2 ] # Colors of the balls a = [ 0 ] + temp_a dp = [ 0 ] * (MAX_N) last_occurrence = [ float ( 'inf' )] * (MAX_N) # Initialize arrays dp[ 0 ] = 0 # Input colors of each ball and calculate DP values for i in range ( 1 , n + 1 ): a[i] = temp_a[i - 1 ] dp[i] = min (dp[i - 1 ] + 1 , last_occurrence[a[i]]) last_occurrence[a[i]] = min (last_occurrence[a[i]], dp[i - 1 ]) # Output the result for the current test case print (n - dp[n]) if __name__ = = "__main__" : main() |
C#
using System; class Program { const int MAX_N = 200000 + 5; static void Main() { int n = 4; // Number of balls int [] tempA = { 1, 2, 1, 2 }; // Colors of the balls int [] a = new int [MAX_N]; int [] dp = new int [MAX_N]; int [] lastOccurrence = new int [MAX_N]; // Initialize arrays dp[0] = 0; for ( int i = 0; i < MAX_N; i++) { lastOccurrence[i] = int .MaxValue; } // Input colors of each ball and calculate DP values for ( int i = 1; i <= n; i++) { a[i] = tempA[i - 1]; dp[i] = Math.Min(dp[i - 1] + 1, lastOccurrence[a[i]]); lastOccurrence[a[i]] = Math.Min(lastOccurrence[a[i]], dp[i - 1]); } // Output the result for the current test case Console.WriteLine(n - dp[n]); } } |
Javascript
const MAX_N = 200000 + 5; let n = 4; // Number of balls let tempA = [1, 2, 1, 2]; // Colors of the balls let a = new Array(MAX_N); let dp = new Array(MAX_N); let lastOccurrence = new Array(MAX_N).fill(Number.MAX_SAFE_INTEGER); // Initialize arrays dp[0] = 0; // Input colors of each ball and calculate DP values for (let i = 1; i <= n; i++) { a[i] = tempA[i - 1]; dp[i] = Math.min(dp[i - 1] + 1, lastOccurrence[a[i]]); lastOccurrence[a[i]] = Math.min(lastOccurrence[a[i]], dp[i - 1]); } // Output the result for the current test case console.log(n - dp[n]); |
3
Time Complexity: O(n), where n is the number of balls.
Auxiliary Space: O(MAX_N)
Contact Us