Dada una array A[] que consta de N enteros, la tarea es encontrar el valor máximo posible de K , tal que K * |i – j| <= min(A i , A j ) , donde (0 ? i < j < N).
Dada la expresión, k * |i – j| <= min(A i , A j ) también se puede escribir como k = piso( min(A i , A j ) / |i – j| )
Ejemplos:
Entrada: N = 5, A[ ] = {80, 10, 12, 15, 90}
Salida: 20
Explicación:
Para i = 0 y j = 4, se puede obtener el máximo valor posible de K.
Máximo k = min(A[0], A[4]) / |0 – 4| = min(80, 90) / |-4| = 80/4 = 20Entrada: N = 5, A[ ] = {10, 5, 12, 15, 8}
Salida: 12
Explicación:
Para i = 2 y j = 3, se puede obtener el máximo valor posible de K.
Máximo k = min(A[2], A[3]) / |2 – 3| = min(12, 15) / |-1| = 12/1 = 12
Enfoque ingenuo:
el enfoque más simple para resolver este problema es generar todos los pares posibles a partir de la array dada y, para cada par, encontrar el valor de K y seguir actualizando el máximo K obtenido. Finalmente, imprima el valor máximo de K obtenido.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, utilice la técnica de dos punteros . Siga los pasos que se indican a continuación:
- Inicialice tres variables i , j y k . Establezca inicialmente i = 0 yk = 0 .
- Iterar sobre la array, desde j = 1 hasta j = N-1 .
- Ahora, para cada par de A[i] y A[j] , encuentre min(A[i], A[j]) / ( j – i ). Si es mayor que K , actualice K .
- Si A[ j ] >= A[i] / ( j – i ) , entonces actualice el puntero i a j , para asegurarse de que entre todos los elementos hasta i , A[i] resulte en un máximo de K con todos los próximos A[ j]
- Finalmente, imprima el valor máximo de K después de que la array se atraviese por completo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function returns maximum
// possible value of k
int solve(int A[], int N)
{
// Pointer i make sure that
// A[i] will result in max k
int i = 0;
// Stores maximum possible k
int k = 0;
for (int j = 1; j < N; j++) {
// Possible value of k for
// current pair (A[i] and A[j])
int tempK = min(A[i], A[j])
/ (j - i);
// If current value exceeds k
if (tempK > k) {
// Update the value of k
k = tempK;
}
// Update pointer i
if (A[j] >= A[i] / (j - i))
i = j;
}
// Return the maxm possible k
return k;
}
// Driver Code
int main()
{
int A[] = { 10, 5, 12, 15, 8 };
int N = sizeof(A) / sizeof(A[0]);
cout << solve(A, N);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG{
// Function returns maximum
// possible value of k
static int solve(int A[], int N)
{
// Pointer i make sure that
// A[i] will result in max k
int i = 0;
// Stores maximum possible k
int k = 0;
for(int j = 1; j < N; j++)
{
// Possible value of k for
// current pair (A[i] and A[j])
int tempK = Math.min(A[i], A[j]) /
(j - i);
// If current value exceeds k
if (tempK > k)
{
// Update the value of k
k = tempK;
}
// Update pointer i
if (A[j] >= A[i] / (j - i))
i = j;
}
// Return the maxm possible k
return k;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 10, 5, 12, 15, 8 };
int N = A.length;
System.out.println(solve(A, N));
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to implement # the above approach # Function returns maximum # possible value of k def solve(A, N): # Pointer i make sure that # A[i] will result in max k i = 0 # Stores maximum possible k k = 0 for j in range(1, N): # Possible value of k for # current pair (A[i] and A[j]) tempK = (min(A[i], A[j]) // (j - i)) # If current value exceeds k if (tempK > k): # Update the value of k k = tempK # Update pointer i if (A[j] >= A[i] // (j - i)): i = j # Return the maxm possible k return k # Driver Code if __name__ == "__main__": A = [ 10, 5, 12, 15, 8 ] N = len(A); print(solve(A, N)) # This code is contributed by chitranayal
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function returns maximum
// possible value of k
static int solve(int[] A, int N)
{
// Pointer i make sure that
// A[i] will result in max k
int i = 0;
// Stores maximum possible k
int k = 0;
for(int j = 1; j < N; j++)
{
// Possible value of k for
// current pair (A[i] and A[j])
int tempK = Math.Min(A[i], A[j]) /
(j - i);
// If current value exceeds k
if (tempK > k)
{
// Update the value of k
k = tempK;
}
// Update pointer i
if (A[j] >= A[i] / (j - i))
i = j;
}
// Return the maxm possible k
return k;
}
// Driver Code
public static void Main(string[] args)
{
int[] A = { 10, 5, 12, 15, 8 };
int N = A.Length;
Console.Write(solve(A, N));
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript program to implement
// the above approach
// Function returns maximum
// possible value of k
function solve(A, N)
{
// Pointer i make sure that
// A[i] will result in max k
let i = 0;
// Stores maximum possible k
let k = 0;
for(let j = 1; j < N; j++)
{
// Possible value of k for
// current pair (A[i] and A[j])
let tempK = Math.min(A[i], A[j]) / (j - i);
// If current value exceeds k
if (tempK > k)
{
// Update the value of k
k = tempK;
}
// Update pointer i
if (A[j] >= A[i] / (j - i))
i = j;
}
// Return the maxm possible k
return k;
}
// Driver code
let A = [ 10, 5, 12, 15, 8 ];
let N = A.length;
document.write(solve(A, N));
// This code is contributed by divyeshrabadiya07
</script>
12
Complejidad temporal: O(N)
Espacio auxiliar: O(1)