Dada una array Arr[ ] de N enteros donde 1 ≤ N ≤ 10 5 . La tarea es elegir cualquier número de elementos de la array tal que:
- Para cada i ( 0≤ i ≥ N-2 ), se debe elegir al menos uno de los elementos i th y (i+1) th .
- Encuentre la mediana máxima posible de enteros de la subsecuencia de la array así formada.
Ejemplos:
Entrada: N = 6, Arr[ ] = { 2, 1, 2, 1, 1, 10 }
Salida: 2
Explicación: Elegir arr[0], arr[2], arr[4] y arr[5] hace que subsecuencia como { 2, 2, 1, 10 } dando mediana como 2 que es el máximo posible. También tenga en cuenta que se cumple la condición de que se debe elegir al menos uno de los dos elementos consecutivos.Entrada: N = 7, Arr[ ] = { 3, 1, 4, 1, 5, 9, 2 }
Salida: 4
Enfoque: El enfoque se basa en la técnica de búsqueda binaria .
- Realice una búsqueda binaria sobre todos los números posibles y verifique si el número actual se puede obtener como una mediana eligiendo cualquier número de elementos de la array bajo la condición dada.
- De todos los valores posibles, el máximo será la respuesta.
- Para verificar si el valor actual x puede ser una mediana o no, siga la simple observación de que si hay más elementos ≥ x en la subsecuencia, entonces la mediana de la subsecuencia es al menos x .
- Después de eso, declare una array modificada de la array original tal que:
- Para cada i ( 0 ≤ i ≤ N-1 ) si Arr[i] ≥ x , entonces modificado[i]=1 ,
- De lo contrario modificado[i] = -1 .
- Ahora, si es posible encontrar una subsecuencia en el arreglo modificado (siguiendo la condición dada de que al menos uno de los i -ésimos y (i+1) -ésimos elementos debe ser elegido) tal que:
- Si la suma de todos los elementos de la subsecuencia es positiva, entonces la corriente x se puede obtener como una mediana .
- La suma de la subsecuencia que es positiva de la array modificada significa que hay más elementos ≥ x , en la array original.
- Por lo tanto, x puede ser una mediana posible.
- Para encontrar si tal suma de subsecuencias se puede obtener de la array modificada, es suficiente encontrar la máxima suma de subsecuencias posible (con la condición dada) de la array modificada y compararla con 0.
- Si es mayor que 0, entonces la x actual puede ser una mediana .
- Para encontrar la suma máxima de subsecuencias , usaremos programación dinámica como se explica en el código.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
int dp[100000 + 5][2];
// Function to find maximum subsequence sum
// from the array under given condition
// using dynamic programming
int max_subsequence_sum(int arr[], int n,
int i, int last)
{
// If we have taken last element already
// then last = 1 else last = 0
if (i >= n) {
return 0;
}
// Already calculated and stored in dp
// ao return directly
if (dp[i][last] != -1) {
return dp[i][last];
}
if (last == 1) {
// Last element is taken already
// so we can either take
// the current element or leave it
int t1 = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
int t2 = max_subsequence_sum(arr, n,
i + 1, 0);
return dp[i][last] = max(t1, t2);
}
else {
// Last element is not taken
// Hence we need to take
// the current element
int t = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
return dp[i][last] = t;
}
}
// Helper function to reset
// dp values for each call
int helper_max_sub_sum(int arr[], int n)
{
memset(dp, -1, sizeof(dp));
int max_sub_sum
= max_subsequence_sum(arr, n, 0, 1);
return max_sub_sum;
}
// Function to check if the given median
// Can be obtained by
// Choosing any subsequence of the array
// Under given constraints
bool is_given_median_possible(int arr[],
int n,
int median)
{
int modified[n];
// Creating the modified array as explained
for (int i{ 0 }; i < n; i++) {
if (arr[i] >= median) {
modified[i] = 1;
}
else {
modified[i] = -1;
}
}
int max_sub_sum
= helper_max_sub_sum(modified, n);
// If max_sub_sum > 0 then current
// median is possible
if (max_sub_sum > 0) {
return true;
}
return false;
}
// Function to binary search
// Over all possible values of median
// To find the max possible median
int binary_search_for_median(int arr[],
int n)
{
int ans = 1;
int low = *min_element(arr, arr + n);
int high = *max_element(arr, arr + n);
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_given_median_possible(arr,
n, mid)) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
int N = 7;
int Arr[] = { 3, 1, 4, 1, 5, 9, 2 };
// Storing the function in ans variable
int ans = binary_search_for_median(Arr, N);
cout << ans << endl;
return 0;
}
Java
// Java code for the above approach
import java.util.*;
class GFG
{
static int dp[][] = new int[100000 + 5][2];
// Function to find maximum subsequence sum
// from the array under given condition
// using dynamic programming
static int max_subsequence_sum(int arr[], int n,
int i, int last)
{
// If we have taken last element already
// then last = 1 else last = 0
if (i >= n) {
return 0;
}
// Already calculated and stored in dp
// ao return directly
if (dp[i][last] != -1) {
return dp[i][last];
}
if (last == 1) {
// Last element is taken already
// so we can either take
// the current element or leave it
int t1 = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
int t2 = max_subsequence_sum(arr, n,
i + 1, 0);
return dp[i][last] = Math.max(t1, t2);
}
else {
// Last element is not taken
// Hence we need to take
// the current element
int t = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
return dp[i][last] = t;
}
}
// Helper function to reset
// dp values for each call
static int helper_max_sub_sum(int arr[], int n)
{
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[i].length;j++){
dp[i][j]= -1;
}
}
int max_sub_sum
= max_subsequence_sum(arr, n, 0, 1);
return max_sub_sum;
}
// Function to check if the given median
// Can be obtained by
// Choosing any subsequence of the array
// Under given constraints
static boolean is_given_median_possible(int arr[],
int n,
int median)
{
int modified[] = new int[n];
// Creating the modified array as explained
for (int i =0; i < n; i++) {
if (arr[i] >= median) {
modified[i] = 1;
}
else {
modified[i] = -1;
}
}
int max_sub_sum
= helper_max_sub_sum(modified, n);
// If max_sub_sum > 0 then current
// median is possible
if (max_sub_sum > 0) {
return true;
}
return false;
}
// Function to binary search
// Over all possible values of median
// To find the max possible median
static int binary_search_for_median(int arr[],
int n)
{
int ans = 1;
int low = 99999999;
int high = -9999999;
for(int i=0;i<arr.length;i++)
{
low = Math.min(low, arr[i]);
high = Math.max(high, arr[i]);
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_given_median_possible(arr,
n, mid)==true) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
public static void main (String[] args) {
int N = 7;
int Arr[] = { 3, 1, 4, 1, 5, 9, 2 };
// Storing the function in ans variable
int ans = binary_search_for_median(Arr, N);
System.out.println( ans);
}
}
// This code is contributed by Potta Lokesh
Python3
# Python code for the above approach # Function to find maximum subsequence sum # from the array under given condition # using dynamic programming def max_subsequence_sum(arr, n, i, last): if i >= n: return 0 if dp[i][last] != -1: return dp[i][last] if last == 1: t1 = arr[i] + max_subsequence_sum(arr, n, i+1, 1) t2 = max_subsequence_sum(arr, n, i+1, 0) dp[i][last] = max(t1, t2) return dp[i][last] else: t = arr[i] + max_subsequence_sum(arr, n, i+1, 1) dp[i][last] = t return dp[i][last] # Helper function to reset # dp values for each call def helper_max_sub_sum(arr, n): global dp dp = [[-1 for i in range(2)] for i in range(100000 + 5)] max_sub_sum = max_subsequence_sum(arr, n, 0, 1) return max_sub_sum # Function to check if the given median # Can be obtained by # Choosing any subsequence of the array # Under given constraints def is_given_median_possible(arr, n, median): modified = [[-1, 1][arr[i] >= median] for i in range(n)] max_sub_sum = helper_max_sub_sum(modified, n) return max_sub_sum > 0 # Function to binary search # Over all possible values of median # To find the max possible median def binary_search_for_median(arr, n): ans = 1 low = min(arr) high = max(arr) while (low <= high): mid = int(low + (high - low)/2) if (is_given_median_possible(arr, n, mid)): ans = mid low = mid + 1 else: high = mid - 1 return ans # Driver Code N = 7 Arr = [3, 1, 4, 1, 5, 9, 2] ans = binary_search_for_median(Arr, N) print(ans) # This code is contributed by phalasi.
C#
// C# code for the above approach
using System;
public class GFG{
static int [,] dp = new int[100000 + 5, 2];
// Function to find maximum subsequence sum
// from the array under given condition
// using dynamic programming
static int max_subsequence_sum(int[] arr, int n,
int i, int last)
{
// If we have taken last element already
// then last = 1 else last = 0
if (i >= n) {
return 0;
}
// Already calculated and stored in dp
// ao return directly
if (dp[i, last] != -1) {
return dp[i, last];
}
if (last == 1) {
// Last element is taken already
// so we can either take
// the current element or leave it
int t1 = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
int t2 = max_subsequence_sum(arr, n,
i + 1, 0);
return dp[i, last] = Math.Max(t1, t2);
}
else {
// Last element is not taken
// Hence we need to take
// the current element
int t = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
return dp[i, last] = t;
}
}
// Helper function to reset
// dp values for each call
static int helper_max_sub_sum(int[] arr, int n)
{
for(int i=0;i<dp.GetLength(0);i++){
for(int j=0;j < dp.GetLength(1);j++){
dp[i, j]= -1;
}
}
int max_sub_sum
= max_subsequence_sum(arr, n, 0, 1);
return max_sub_sum;
}
// Function to check if the given median
// Can be obtained by
// Choosing any subsequence of the array
// Under given constraints
static bool is_given_median_possible(int[] arr,
int n,
int median)
{
int[] modified = new int[n];
// Creating the modified array as explained
for (int i =0; i < n; i++) {
if (arr[i] >= median) {
modified[i] = 1;
}
else {
modified[i] = -1;
}
}
int max_sub_sum
= helper_max_sub_sum(modified, n);
// If max_sub_sum > 0 then current
// median is possible
if (max_sub_sum > 0) {
return true;
}
return false;
}
// Function to binary search
// Over all possible values of median
// To find the max possible median
static int binary_search_for_median(int[] arr,
int n)
{
int ans = 1;
int low = 99999999;
int high = -9999999;
for(int i=0;i<arr.Length;i++)
{
low = Math.Min(low, arr[i]);
high = Math.Max(high, arr[i]);
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (is_given_median_possible(arr,
n, mid)==true) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
static public void Main (){
int N = 7;
int[] Arr = { 3, 1, 4, 1, 5, 9, 2 };
// Storing the function in ans variable
int ans = binary_search_for_median(Arr, N);
Console.Write( ans);
}
}
// This code is contributed by hrithikgarg0388.
Javascript
<script>
// JavaScript code for the above approach:
let dp = new Array(100000 + 5).fill(0).map(() => new Array(2).fill(0));
// Function to find maximum subsequence sum
// from the array under given condition
// using dynamic programming
const max_subsequence_sum = (arr, n, i, last) => {
// If we have taken last element already
// then last = 1 else last = 0
if (i >= n) {
return 0;
}
// Already calculated and stored in dp
// ao return directly
if (dp[i][last] != -1) {
return dp[i][last];
}
if (last == 1) {
// Last element is taken already
// so we can either take
// the current element or leave it
let t1 = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
let t2 = max_subsequence_sum(arr, n,
i + 1, 0);
return dp[i][last] = Math.max(t1, t2);
}
else {
// Last element is not taken
// Hence we need to take
// the current element
let t = arr[i]
+ max_subsequence_sum(arr, n,
i + 1, 1);
return dp[i][last] = t;
}
}
// Helper function to reset
// dp values for each call
const helper_max_sub_sum = (arr, n) => {
for (let i = 0; i < dp.length; ++i) {
for (let j = 0; j < dp[0].length; ++j) dp[i][j] = -1;
}
let max_sub_sum
= max_subsequence_sum(arr, n, 0, 1);
return max_sub_sum;
}
// Function to check if the given median
// Can be obtained by
// Choosing any subsequence of the array
// Under given constraints
const is_given_median_possible = (arr, n, median) => {
let modified = new Array(n).fill(0);
// Creating the modified array as explained
for (let i = 0; i < n; i++) {
if (arr[i] >= median) {
modified[i] = 1;
}
else {
modified[i] = -1;
}
}
let max_sub_sum
= helper_max_sub_sum(modified, n);
// If max_sub_sum > 0 then current
// median is possible
if (max_sub_sum > 0) {
return true;
}
return false;
}
// Function to binary search
// Over all possible values of median
// To find the max possible median
const binary_search_for_median = (arr, n) => {
let ans = 1;
let low = Math.min(...arr);
let high = Math.max(...arr);
while (low <= high) {
let mid = low + parseInt((high - low) / 2);
if (is_given_median_possible(arr,
n, mid)) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
return ans;
}
// Driver code
let N = 7;
let Arr = [3, 1, 4, 1, 5, 9, 2];
// Storing the function in ans variable
let ans = binary_search_for_median(Arr, N);
document.write(ans);
// This code is contributed by rakeshsahni
</script>
Producción
4
Complejidad de tiempo: O(N* log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anilyogi2801 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA