Queries to find longest subsequence having no similar adjacent elements with updates | Java program for the above approach ; Traverse the array arr [ ] ; If previous element is not same as current element ; Traverse the queries ; Replace element at index x with y ; Recalculate for index x ; Subtract contribution of element at index x ; Add contribution of y ; Recalculate for index x + 1 ; Subtract contribution of element at index x + 1 ; Adds contribution of y ; Replace the element ; Driver Code ; Function Call
import java . util . * ; class GFG { static void longestSubsequence ( int N , int Q , int arr [ ] , int Queries [ ] [ ] ) { int count = 1 ; for ( int i = 1 ; i < N ; i ++ ) { if ( arr [ i ] != arr [ i - 1 ] ) { count += 1 ; } } for ( int i = 0 ; i < Q ; i ++ ) { int x = Queries [ i ] [ 0 ] ; int y = Queries [ i ] [ 1 ] ; if ( x > 1 ) { if ( arr [ x - 1 ] != arr [ x - 2 ] ) { count -= 1 ; } if ( arr [ x - 2 ] != y ) { count += 1 ; } } if ( x < N ) { if ( arr [ x ] != arr [ x - 1 ] ) { count -= 1 ; } if ( y != arr [ x ] ) { count += 1 ; } } System . out . print ( count + " ▁ " ) ; arr [ x - 1 ] = y ; } } public static void main ( String args [ ] ) { int arr [ ] = { 1 , 1 , 2 , 5 , 2 } ; int N = arr . length ; int Q = 2 ; int Queries [ ] [ ] = { { 1 , 3 } , { 4 , 2 } } ; longestSubsequence ( N , Q , arr , Queries ) ; } }