Maximize the sum of array by multiplying prefix of array with | C ++ implementation of the approach ; To store sum ; To store ending indices of the chosen prefix array vect ; Adding the absolute value of a [ i ] ; If i == 0 then there is no index to be flipped in ( i - 1 ) position ; print the maximized sum ; print the ending indices of the chosen prefix arrays ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxSum ( int * a , int n ) { vector < int > l ; int s = 0 ; for ( int i = 0 ; i < n ; i ++ ) { s += abs ( a [ i ] ) ; if ( a [ i ] >= 0 ) continue ; if ( i == 0 ) l . push_back ( i + 1 ) ; else { l . push_back ( i + 1 ) ; l . push_back ( i ) ; } } cout << s << endl ; for ( int i = 0 ; i < l . size ( ) ; i ++ ) cout << l [ i ] << " ▁ " ; } int main ( ) { int n = 4 ; int a [ ] = { 1 , -2 , -3 , 4 } ; maxSum ( a , n ) ; }