Chocolate Distribution Problem | Set 2 | C ++ program for above approach ; Function to return minimum number of chocolates ; decreasing sequence ; add the chocolates received by that person ; end point of decreasing sequence ; val = 1 ; reset value at that index ; increasing sequence ; flat sequence ; add value of chocolates at position n - 1 ; Helper function to get sum of decreasing sequence ; value obtained from decreasing sequence also the count of values in the sequence ; assigning max of values obtained from increasing and decreasing sequences ; sum of count - 1 values & peak value sum of natural numbers : ( n * ( n + 1 ) ) / 2 ; Driver code
#include <iostream> NEW_LINE using namespace std ; int minChocolates ( int a [ ] , int n ) { int i = 0 , j = 0 ; int res = 0 , val = 1 ; while ( j < n - 1 ) { if ( a [ j ] > a [ j + 1 ] ) { j += 1 ; continue ; } if ( i == j ) res += val ; else { res += get_sum ( val , i , j ) ; } if ( a [ j ] < a [ j + 1 ] ) val += 1 ; else val = 1 ; j += 1 ; i = j ; } if ( i == j ) res += val ; else res += get_sum ( val , i , j ) ; return res ; } int get_sum ( int peak , int start , int end ) { int count = end - start + 1 ; peak = max ( peak , count ) ; int s = peak + ( ( ( count - 1 ) * count ) >> 1 ) ; return s ; } int main ( ) { int a [ ] = { 5 , 5 , 4 , 3 , 2 , 1 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << " Minimum ▁ number ▁ of ▁ chocolates ▁ = ▁ " << minChocolates ( a , n ) << " STRNEWLINE " ; return 0 ; }