Maximum length Subsequence with alternating sign and maximum Sum | C ++ implementation to find the subsequence with alternating sign having maximum size and maximum sum . ; Function to find the subsequence with alternating sign having maximum size and maximum sum . ; Find whether each element is positive or negative ; Find the required subsequence ; Find the maximum element in the specified range ; print the result ; Driver code ; array declaration ; size of array
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findSubsequence ( int arr [ ] , int n ) { int sign [ n ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { if ( arr [ i ] > 0 ) sign [ i ] = 1 ; else sign [ i ] = -1 ; } int k = 0 ; int result [ n ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int cur = arr [ i ] ; int j = i ; while ( j < n && sign [ i ] == sign [ j ] ) { cur = max ( cur , arr [ j ] ) ; ++ j ; } result [ k ++ ] = cur ; i = j - 1 ; } for ( int i = 0 ; i < k ; i ++ ) cout << result [ i ] << " ▁ " ; cout << " STRNEWLINE " ; } int main ( ) { int arr [ ] = { -4 , 9 , 4 , 11 , -5 , -17 , 9 , -3 , -5 , 2 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findSubsequence ( arr , n ) ; return 0 ; }