Dada una array arr[] . La tarea es encontrar la puntuación máxima que se puede lograr desde arr[] para i=[1, N-2] . Las condiciones para la puntuación se dan a continuación.
- Si arr[0…j] < arr[i] < arr[i+1…N-1] , entonces puntuación = 2 .
- Si arr[i-1] < arr[i] < arr[i+1] y la condición anterior no se cumple, entonces la puntuación = 1 .
- Si ninguna de las condiciones se cumple, entonces la puntuación = 0 .
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 2
Explicación: La puntuación de arr[1] es igual a 2, que es el máximo posible.Entrada: arr[] = {2, 4, 6, 4}
Salida : 1
Explicación: Para cada índice i en el rango 1 <= i <= 2:
La puntuación de nums[1] es igual a 1.
La puntuación de nums[ 2] es igual a 0.
Por lo tanto, 1 es la puntuación máxima posible.
Enfoque: este problema se puede resolver utilizando Prefix Max y Suffix Min. Siga los pasos a continuación para resolver el problema dado.
- Para que la puntuación de un elemento sea 2 , debe ser mayor que todos los elementos a su izquierda y menor que todos los elementos a su derecha.
- Por lo tanto, precalcule para encontrar el prefijo máximo y el sufijo mínimo para cada elemento de la array.
- Ahora verifique cada elemento de la array arr[] en i :
- Si es mayor que el prefijo max en i-1 y menor que el sufijo min en i+1 , la puntuación será 2 .
- de lo contrario, si es mayor que arr[i-1] y menor que arr[i+1] , la puntuación será 1 .
- de lo contrario, la puntuación será 0 .
- Suma todos los puntajes y devuélvelo como la respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum score
int maxScore(vector<int>& nums)
{
// Size of array
int n = nums.size(), i;
int ans = 0;
// Prefix max
vector<int> pre(n, 0);
// Suffix min
vector<int> suf(n, 0);
pre[0] = nums[0];
for (i = 1; i < n; i++)
pre[i] = max(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (i = n - 2; i >= 0; i--)
suf[i] = min(suf[i + 1], nums[i]);
for (i = 1; i < n - 1; i++) {
if (nums[i] > pre[i - 1]
&& nums[i] < suf[i + 1])
ans += 2;
else if (nums[i] > nums[i - 1]
&& nums[i] < nums[i + 1])
ans += 1;
}
return ans;
}
// Driver Code
int main()
{
int N = 3;
vector<int> arr = { 1, 2, 3 };
// Function Call
cout << maxScore(arr);
return 0;
}
Java
// Java program for above approach
import java.util.*;
public class GFG
{
// Function to find maximum score
static int maxScore(ArrayList<Integer> nums)
{
// Size of array
int n = nums.size(), i = 0;
int ans = 0;
// Prefix max
int[] pre = new int[n];
// Suffix min
int[] suf = new int[n];
pre[0] = (int)nums.get(0);
for (i = 1; i < n; i++)
pre[i] = Math.max(pre[i - 1], (int)nums.get(i));
suf[n - 1] = (int)nums.get(n - 1);
for (i = n - 2; i >= 0; i--)
suf[i] = Math.min(suf[i + 1], (int)nums.get(i));
for (i = 1; i < n - 1; i++) {
if ((int)nums.get(i) > pre[i - 1]
&& (int)nums.get(i) < suf[i + 1])
ans += 2;
else if ((int)nums.get(i) > (int)nums.get(i - 1)
&& (int)nums.get(i) < (int)nums.get(i + 1))
ans += 1;
}
return ans;
}
// Driver Code
public static void main(String args[])
{
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(1);
arr.add(2);
arr.add(3);
// Function Call
System.out.println(maxScore(arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python program for above approach # Function to find maximum score def maxScore(nums): # Size of array n = len(nums) ans = 0 # Prefix max pre = [0 for _ in range(n)] # Suffix min suf = [0 for _ in range(n)] pre[0] = nums[0] for i in range(1, n): pre[i] = max(pre[i - 1], nums[i]) suf[n - 1] = nums[n - 1] for i in range(n-2, -1, -1): suf[i] = min(suf[i + 1], nums[i]) for i in range(1, n-1): if (nums[i] > pre[i - 1] and nums[i] < suf[i + 1]): ans += 2 elif (nums[i] > nums[i - 1] and nums[i] < nums[i + 1]): ans += 1 return ans # Driver Code if __name__ == "__main__": N = 3 arr = [1, 2, 3] # Function Call print(maxScore(arr)) # This code is contributed by rakeshsahni
C#
// C# program for above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find maximum score
static int maxScore(List<int> nums)
{
// Size of array
int n = nums.Count, i = 0;
int ans = 0;
// Prefix max
int[] pre = new int[n];
// Suffix min
int[] suf = new int[n];
pre[0] = nums[0];
for (i = 1; i < n; i++)
pre[i] = Math.Max(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (i = n - 2; i >= 0; i--)
suf[i] = Math.Min(suf[i + 1], nums[i]);
for (i = 1; i < n - 1; i++) {
if (nums[i] > pre[i - 1]
&& nums[i] < suf[i + 1])
ans += 2;
else if (nums[i] > nums[i - 1]
&& nums[i] < nums[i + 1])
ans += 1;
}
return ans;
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>() { 1, 2, 3 };
// Function Call
Console.WriteLine(maxScore(arr));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to find maximum score
function maxScore(nums) {
// Size of array
let n = nums.length, i;
let ans = 0;
// Prefix max
let pre = new Array(n).fill(0)
// Suffix min
let suf = new Array(n).fill(0);
pre[0] = nums[0];
for (i = 1; i < n; i++)
pre[i] = Math.max(pre[i - 1], nums[i]);
suf[n - 1] = nums[n - 1];
for (i = n - 2; i >= 0; i--)
suf[i] = Math.min(suf[i + 1], nums[i]);
for (i = 1; i < n - 1; i++) {
if (nums[i] > pre[i - 1]
&& nums[i] < suf[i + 1])
ans += 2;
else if (nums[i] > nums[i - 1]
&& nums[i] < nums[i + 1])
ans += 1;
}
return ans;
}
// Driver Code
let N = 3;
let arr = [1, 2, 3];
// Function Call
document.write(maxScore(arr));
// This code is contributed by Potta Lokesh
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)