Maximum number of candies that can be bought | C ++ implementation of the approach ; Function to return the maximum candies that can be bought ; Buy all the candies of the last type ; Starting from second last ; Amount of candies of the current type that can be bought ; Add candies of current type that can be bought ; Update the previous bought amount ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxCandies ( int arr [ ] , int n ) { int prevBought = arr [ n - 1 ] ; int candies = prevBought ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int x = min ( prevBought - 1 , arr [ i ] ) ; if ( x >= 0 ) { candies += x ; prevBought = x ; } } return candies ; } int main ( ) { int arr [ ] = { 1 , 2 , 1 , 3 , 6 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxCandies ( arr , n ) ; return 0 ; }