# Maximum number of candies that can be bought

Given an array **arr[]** of size **n** where **arr[i]** is the number of candies of type **i**. You have an unlimited amount of money. The task is to buy as many candies as possible satisfying the following conditions:

If you buy **x(i)** candies of type **i** (clearly, 0 ≤ x(i) ≤ arr[i]), then for all **j** (1 ≤ j ≤ i) at least one of the following must hold:

**x(j) < x(i)**(you bought less candies of type j than of type i)**x(j) = 0**(you bought 0 candies of type j)

**Examples:**

Input:arr[] = {1, 2, 1, 3, 6}Output:10

x[] = {0, 0, 1, 3, 6} where x[i] is the number of candies bought of type iInput:arr[] = {3, 2, 5, 4, 10}Output:20Input:arr[] = {1, 1, 1, 1}Output:1

**Approach:** We can use a greedy approach and start from the end of the array. If we have taken **x** candies of type **i + 1** then we can only take **min(arr[i], x – 1)** candies of type **i**. If this value is negative, we cannot buy candies of the current type.

Below is the implementation of the above approach:

## C++

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

## Java

`// Java implementation of the approach` `class` `GFG` `{` ` ` `// Function to return the maximum candies` `// that can be bought` `static` `int` `maxCandies(` `int` `arr[], ` `int` `n)` `{` ` ` `// Buy all the candies of the last type` ` ` `int` `prevBought = arr[n - ` `1` `];` ` ` `int` `candies = prevBought;` ` ` `// 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 = Math.min(prevBought - ` `1` `, arr[i]);` ` ` `if` `(x >= ` `0` `)` ` ` `{` ` ` `// Add candies of current type` ` ` `// that can be bought` ` ` `candies += x;` ` ` `// Update the previous bought amount` ` ` `prevBought = x;` ` ` `}` ` ` `}` ` ` `return` `candies;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = { ` `1` `, ` `2` `, ` `1` `, ` `3` `, ` `6` `};` ` ` `int` `n = arr.length;` ` ` `System.out.println(maxCandies(arr, n));` `}` `}` `// This code is contributed by Code_Mech.` |

## Python3

`# Python3 implementation of the approach` `# Function to return the maximum candies` `# that can be bought` `def` `maxCandies(arr, n) :` ` ` ` ` `# Buy all the candies of the last type` ` ` `prevBought ` `=` `arr[n ` `-` `1` `];` ` ` `candies ` `=` `prevBought;` ` ` ` ` `# Starting from second last` ` ` `for` `i ` `in` `range` `(n ` `-` `2` `, ` `-` `1` `, ` `-` `1` `) :` ` ` ` ` `# Amount of candies of the current` ` ` `# type that can be bought` ` ` `x ` `=` `min` `(prevBought ` `-` `1` `, arr[i]);` ` ` `if` `(x >` `=` `0` `) :` ` ` ` ` `# Add candies of current type` ` ` `# that can be bought` ` ` `candies ` `+` `=` `x;` ` ` ` ` `# Update the previous bought amount` ` ` `prevBought ` `=` `x;` ` ` ` ` `return` `candies;` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` ` ` `arr ` `=` `[ ` `1` `, ` `2` `, ` `1` `, ` `3` `, ` `6` `];` ` ` `n ` `=` `len` `(arr)` ` ` `print` `(maxCandies(arr, n));` `# This code is contributed by Ryuga` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to return the maximum candies` `// that can be bought` `static` `int` `maxCandies(` `int` `[] arr, ` `int` `n)` `{` ` ` `// Buy all the candies of the last type` ` ` `int` `prevBought = arr[n - 1];` ` ` `int` `candies = prevBought;` ` ` `// 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 = Math.Min(prevBought - 1, arr[i]);` ` ` `if` `(x >= 0)` ` ` `{` ` ` `// Add candies of current type` ` ` `// that can be bought` ` ` `candies += x;` ` ` `// Update the previous bought amount` ` ` `prevBought = x;` ` ` `}` ` ` `}` ` ` `return` `candies;` `}` `// Driver code` `public` `static` `void` `Main()` `{` ` ` `int` `[] arr= { 1, 2, 1, 3, 6 };` ` ` `int` `n = arr.Length;` ` ` `Console.WriteLine(maxCandies(arr, n));` `}` `}` `// This code is contributed by Code_Mech.` |

## PHP

`<?php` `// PHP implementation of the approach` `// Function to return the maximum candies` `// that can be bought` `function` `maxCandies(` `$arr` `, ` `$n` `)` `{` ` ` `// Buy all the candies of the last type` ` ` `$prevBought` `= ` `$arr` `[` `$n` `- 1];` ` ` `$candies` `= ` `$prevBought` `;` ` ` `// Starting from second last` ` ` `for` `(` `$i` `= ` `$n` `- 2; ` `$i` `>= 0; ` `$i` `--)` ` ` `{` ` ` `// Amount of candies of the current` ` ` `// type that can be bought` ` ` `$x` `= min(` `$prevBought` `- 1, ` `$arr` `[` `$i` `]);` ` ` `if` `(` `$x` `>= 0)` ` ` `{` ` ` `// Add candies of current type` ` ` `// that can be bought` ` ` `$candies` `+= ` `$x` `;` ` ` `// Update the previous bought amount` ` ` `$prevBought` `= ` `$x` `;` ` ` `}` ` ` `}` ` ` `return` `$candies` `;` `}` `// Driver code` `$arr` `= ` `array` `(1, 2, 1, 3, 6 );` `$n` `= sizeof(` `$arr` `);` `echo` `(maxCandies(` `$arr` `, ` `$n` `));` `// This code is contributed by Code_Mech.` `?>` |

## Javascript

`<script>` `// Javascript implementation of the approach` `// Function to return the maximum candies` `// that can be bought` `function` `maxCandies(arr, n)` `{` ` ` ` ` `// Buy all the candies of the last type` ` ` `let prevBought = arr[n - 1];` ` ` `let candies = prevBought;` ` ` ` ` `// Starting from second last` ` ` `for` `(let i = n - 2; i >= 0; i--)` ` ` `{` ` ` ` ` `// Amount of candies of the current` ` ` `// type that can be bought` ` ` `let x = Math.min(prevBought - 1, arr[i]);` ` ` ` ` `if` `(x >= 0)` ` ` `{` ` ` ` ` `// Add candies of current type` ` ` `// that can be bought` ` ` `candies += x;` ` ` ` ` `// Update the previous bought amount` ` ` `prevBought = x;` ` ` `}` ` ` `}` ` ` ` ` `return` `candies;` `} ` ` ` `// Driver Code` ` ` `let arr = [ 1, 2, 1, 3, 6 ];` ` ` `let n = arr.length;` ` ` `document.write(maxCandies(arr, n));` ` ` `</script>` |

**Output:**

10