Dada una array arr[] de tamaño n donde arr[i] es el número de dulces de tipo i . Tienes una cantidad ilimitada de dinero. La tarea es comprar tantos dulces como sea posible que satisfagan las siguientes condiciones:
Si compra x(i) dulces de tipo i (claramente, 0 ≤ x(i) ≤ arr[i]), entonces para todo j (1 ≤ j ≤ i) al menos uno de los siguientes debe cumplir:
- x(j) < x(i) (compraste menos dulces del tipo j que del tipo i)
- x(j) = 0 (compraste 0 caramelos del tipo j)
Ejemplos:
Entrada: arr[] = {1, 2, 1, 3, 6}
Salida: 10
x[] = {0, 0, 1, 3, 6} donde x[i] es el número de dulces comprados del tipo i
Entrada : arr[] = {3, 2, 5, 4, 10}
Salida: 20
Entrada: arr[] = {1, 1, 1, 1}
Salida: 1
Enfoque: podemos usar un enfoque codicioso y comenzar desde el final de la array. Si hemos tomado x dulces de tipo i + 1 , entonces solo podemos tomar min(arr[i], x – 1) dulces de tipo i . Si este valor es negativo, no podemos comprar caramelos del tipo actual.
A continuación se muestra la implementación del enfoque anterior:
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>
10
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anshuman_7 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA