Maximum sum alternating subsequence | Java program to find sum of maximum sum alternating sequence starting with first element . ; Return sum of maximum sum alternating sequence starting with arr [ 0 ] and is first decreasing . ; handling the edge case ; stores sum of decreasing and increasing sub - sequence ; store sum of increasing and decreasing sun - sequence ; As per question , first element must be part of solution . ; Traverse remaining elements of array ; IF current sub - sequence is decreasing the update dec [ j ] if needed . dec [ i ] by current inc [ j ] + arr [ i ] ; Revert the flag , if first decreasing is found ; If next element is greater but flag should be 1 i . e . this element should be counted after the first decreasing element gets counted ; If current sub - sequence is increasing then update inc [ i ] ; find maximum sum in b / w inc [ ] and dec [ ] ; return maximum sum alternate sun - sequence ; Driver Method
public class GFG { static int maxAlternateSum ( int arr [ ] , int n ) { if ( n == 1 ) return arr [ 0 ] ; int min = arr [ 0 ] ; for ( int i = 1 ; i < n ; i ++ ) { if ( min > arr [ i ] ) min = arr [ i ] ; } if ( min == arr [ 0 ] ) { return arr [ 0 ] ; } int dec [ ] = new int [ n ] ; int inc [ ] = new int [ n ] ; dec [ 0 ] = inc [ 0 ] = arr [ 0 ] ; int flag = 0 ; for ( int i = 1 ; i < n ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( arr [ j ] > arr [ i ] ) { dec [ i ] = Math . max ( dec [ i ] , inc [ j ] + arr [ i ] ) ; flag = 1 ; } else if ( arr [ j ] < arr [ i ] && flag == 1 ) inc [ i ] = Math . max ( inc [ i ] , dec [ j ] + arr [ i ] ) ; } } int result = Integer . MIN_VALUE ; for ( int i = 0 ; i < n ; i ++ ) { if ( result < inc [ i ] ) result = inc [ i ] ; if ( result < dec [ i ] ) result = dec [ i ] ; } return result ; } public static void main ( String [ ] args ) { int arr [ ] = { 8 , 2 , 3 , 5 , 7 , 9 , 10 } ; System . out . println ( " Maximum ▁ sum ▁ = ▁ " + maxAlternateSum ( arr , arr . length ) ) ; } }