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

The integer array candies[] is used to store the number of candies of type i.

The variable 'size' stores the length of the array candies.

The function maxCandies(int arr[], int n) is used to return the total number of candies that can be purchased.

First suppose we buy the last candy. buy=arr[n-1]

Start from the penultimate element, for(i=n-2;i>=0;i--)

Variable x stores the number of candies that can be purchased of the current type. x=arr[i] or buy-1, whichever is smaller.

If x is not zeo, add it to the total.

If the sum is greater than the amount of the previous purchase, purchase = x.

Return purchase results.

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!