Maximum sum alternating subsequence | 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 program
def maxAlternateSum ( arr , n ) : NEW_LINE INDENT if ( n == 1 ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT min = arr [ 0 ] NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT if ( min > arr [ i ] ) : NEW_LINE INDENT min = arr [ i ] NEW_LINE DEDENT DEDENT if ( arr [ 0 ] == min ) : NEW_LINE INDENT return arr [ 0 ] NEW_LINE DEDENT dec = [ 0 for i in range ( n + 1 ) ] NEW_LINE inc = [ 0 for i in range ( n + 1 ) ] NEW_LINE dec [ 0 ] = inc [ 0 ] = arr [ 0 ] NEW_LINE flag = 0 NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ j ] > arr [ i ] ) : NEW_LINE INDENT dec [ i ] = max ( dec [ i ] , inc [ j ] + arr [ i ] ) NEW_LINE flag = 1 NEW_LINE DEDENT elif ( arr [ j ] < arr [ i ] and flag == 1 ) : NEW_LINE INDENT inc [ i ] = max ( inc [ i ] , dec [ j ] + arr [ i ] ) NEW_LINE DEDENT DEDENT DEDENT result = - 2147483648 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( result < inc [ i ] ) : NEW_LINE INDENT result = inc [ i ] NEW_LINE DEDENT if ( result < dec [ i ] ) : NEW_LINE INDENT result = dec [ i ] NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT arr = [ 8 , 2 , 3 , 5 , 7 , 9 , 10 ] NEW_LINE n = len ( arr ) NEW_LINE print ( " Maximum ▁ sum ▁ = ▁ " , maxAlternateSum ( arr , n ) ) NEW_LINE