Maximum number of candies that can be purchased

We get a candy[] array with the length stored in "size". Each element of candies[i] has a number for a candy of type i. The goal is to buy as many candies as possible with any amount of money. The conditions are as follows -

If you buy X[i] of type i (0

• X(j)

• X(j)=0, no candy of type j was purchased

We understand through examples.

Input - Arr[] = { 1,3,5,2,6,7}.

Output - Maximum number of candies that can be purchased - 16

Description - Purchase type i { 0,3,5,2,6, 0 }

's Candy>Input - Arr[] = { 5,7,7,3,4 }.

Output - OK Maximum candies purchased - 10

Explanation - Purchase candies of type i { 0,0,7,3,0 }

The method used in the following program is as follows

Example

Live Demonstration

#include <stdio.h>
int maxCandies(int arr[], int n){
   int bought = arr[n - 1];
   int total = bought;
   // Starting from second last
   for (int i = n - 2; i >= 0; i--) {
      // Amount of candies of the current
      // type that can be bought
      int x = arr[i]<bought-1?arr[i]:bought-1;
      if (x >= 0) {
         total += x;
         bought = x;
      }
   }
   return total;
}
int main(){
   int candies[] = { 1,2,4,3,7 };
   int size = 5;
   printf("Total Candies that can be bought: %d", maxCandies(candies, size));
   return 0;
}

Output

If we run the above code, it will generate the following output-

Total Candies that can be bought: 13

The above is the detailed content of Maximum number of candies that can be purchased. For more information, please follow other related articles on the PHP Chinese website!