Minimum sum possible by assigning every increasing / decreasing consecutive pair with values in that order | C ++ program for the above approach ; Function to print the minimum sum of values assigned to each element of the array as per given conditions ; Initialize vectors with value 1 ; Traverse from left to right ; Update if ans [ i ] > ans [ i - 1 ] ; Traverse from right to left ; Update as ans [ i ] > ans [ i + 1 ] if arr [ i ] > arr [ i + 1 ] ; Find the minimum sum ; Print the sum ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void minSum ( int * arr , int n ) { vector < int > ans ( n , 1 ) ; for ( int i = 1 ; i < n ; i ++ ) { if ( arr [ i ] > arr [ i - 1 ] ) { ans [ i ] = max ( ans [ i ] , ans [ i - 1 ] + 1 ) ; } } for ( int i = n - 2 ; i >= 0 ; i -- ) { if ( arr [ i ] > arr [ i + 1 ] ) { ans [ i ] = max ( ans [ i ] , ans [ i + 1 ] + 1 ) ; } } int s = 0 ; for ( auto x : ans ) { s = s + x ; } cout << s << endl ; } int main ( ) { int arr [ ] = { 1 , 2 , 2 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; minSum ( arr , N ) ; return 0 ; }