Dada una array binaria nums de longitud N, la tarea es encontrar todas las particiones posibles en una array dada de tal manera que se maximice la suma de la cuenta de 0 en la parte izquierda y la cuenta de 1 en la parte derecha.
Ejemplo :
Entrada : nums = {0, 0, 1, 0}
Salida : 2, 4
Explicación : División en índice
índice – 0: numsleft es []. numsright es [0, 0, 1, 0]. La suma es 0 + 1 = 1.
índice – 1: numsleft es [0]. numsright es [0, 1, 0]. La suma es 1 + 1 = 2.
índice – 2: numsleft es [0, 0]. numsright es [1, 0]. La suma es 2 + 1 = 3.
índice – 3: numsleft es [0, 0, 1]. el número correcto es [0]. La suma es 2 + 0 = 2.
índice – 4: numsleft es [0, 0, 1, 0]. numsright es []. La suma es 3 + 0 = 3.
Por lo tanto, la partición en el índice 2 y 4 da la suma más alta posible 3.Entrada : nums= {0, 0, 0, 1, 0, 1, 1}
Salida : 3, 5
Explicación :
si dividimos la array en el índice 3, entonces numsLeft es 3 y numsRight es 3. La suma es 3 + 3 = 6
Si dividimos la array en el índice 5, numsLeft es 4 y numsRight es 2. La suma es 4 + 2 = 6
Cualquier otra división dará como resultado una puntuación inferior a 6.
Enfoque : La idea es usar el prefijo sum tal que sum[i+1] sea A[0] + … + A[i].
- Encuentre la suma del prefijo de la array y guárdela en la suma de la array.
- Para cada índice i, habrá i – sum[i] ceros en la parte izquierda y sum[N] – sum[i] unos en la parte derecha.
- Calcule la puntuación sumando la parte izquierda y la parte derecha.
- Compara la puntuación con la puntuación máxima anterior
- si el puntaje actual es mayor que el anterior, actualice el puntaje máximo y coloque i en la array de resultados.
- si el puntaje actual es igual al máximo anterior, entonces en la array de resultados anterior presione este índice i.
- Devuelve la array resultante después de completar el recorrido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find partitions
// that maximizes sum of count of 0's
// in left part and count
// of 1's in right part
#include <bits/stdc++.h>
using namespace std;
// Function to find all possible
// max sum partitions
vector<int> findPartitions(vector<int>& A)
{
int N = A.size(), mx = 0;
// Prefix sum array
vector<int> sum(N + 1, 0), ans;
for (int i = 0; i < N; ++i)
sum[i + 1] = sum[i] + A[i];
// Find the partitions
// with maximum prefix sum
for (int i = 0; i <= N; ++i) {
// Calculate score for
// the current index
int score = i - sum[i]
+ sum[N] - sum[i];
// Compare current score
// with previous max
if (score > mx) {
ans = { i };
mx = score;
}
// If current score
// is greater than
// previous then push
// in the ans array.
else if (score == mx)
ans.push_back(i);
}
// Returning the resultant
// array of indices
return ans;
}
// Driver code
int main()
{
vector<int> res,
arr{ 0, 0, 0, 1, 0, 1, 1 };
res = findPartitions(arr);
for (auto it : res)
cout << it << " ";
return 0;
}
Java
// Java program to find partitions
// that maximizes sum of count of 0's
// in left part and count
// of 1's in right part
import java.util.*;
class GFG{
// Function to find all possible
// max sum partitions
static Vector<Integer>findPartitions(int []A)
{
int N = A.length, mx = 0;
// Prefix sum array
Vector<Integer> ans = new Vector<Integer>();
int []sum = new int[N + 1];
for (int i = 0; i < N; ++i)
sum[i + 1] = sum[i] + A[i];
// Find the partitions
// with maximum prefix sum
for (int i = 0; i <= N; ++i) {
// Calculate score for
// the current index
int score = i - sum[i]
+ sum[N] - sum[i];
// Compare current score
// with previous max
if (score > mx) {
ans = new Vector<Integer>();
ans.add(i);
mx = score;
}
// If current score
// is greater than
// previous then push
// in the ans array.
else if (score == mx)
ans.add(i);
}
// Returning the resultant
// array of indices
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 0, 0, 0, 1, 0, 1, 1 };
Vector<Integer> res = findPartitions(arr);
for (int it : res)
System.out.print(it+ " ");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to find partitions # that maximizes sum of count of 0's # in left part and count # of 1's in right part # Function to find all possible # max sum partitions def findPartitions(A): N = len(A) mx = 0 # Prefix sum array sum = [] for i in range(0, N + 1): sum.append(0) ans = [] for i in range(0, N): sum[i + 1] = sum[i] + A[i]; # Find the partitions # with maximum prefix sum for i in range(0, N + 1): # Calculate score for # the current index score = i - sum[i] + sum[N] - sum[i] # Compare current score # with previous max if (score > mx): ans.clear() ans.append(i) mx = score # If current score # is greater than # previous then push # in the ans array. elif (score == mx): ans.append(i) # Returning the resultant # array of indices return ans # Driver code res = [] arr = [ 0, 0, 0, 1, 0, 1, 1 ] res = findPartitions(arr) print(res) # This code is contributed by Samim Hossain Mondal
C#
// C# program to find partitions
// that maximizes sum of count of 0's
// in left part and count
// of 1's in right part
using System;
using System.Collections;
class GFG
{
// Function to find all possible
// max sum partitions
static ArrayList findPartitions(ArrayList A)
{
int N = A.Count, mx = 0;
// Prefix sum array
int []sum = new int[N + 1];
for(int i = 0; i < N + 1; i++) {
sum[i] = 0;
}
ArrayList ans = new ArrayList();
for (int i = 0; i < N; ++i)
sum[i + 1] = sum[i] + (int)A[i];
// Find the partitions
// with maximum prefix sum
for (int i = 0; i <= N; ++i) {
// Calculate score for
// the current index
int score = i - sum[i]
+ sum[N] - sum[i];
// Compare current score
// with previous max
if (score > mx) {
ans.Clear();
ans.Add(i);
mx = score;
}
// If current score
// is greater than
// previous then push
// in the ans array.
else if (score == mx)
ans.Add(i);
}
// Returning the resultant
// array of indices
return ans;
}
// Driver code
public static void Main()
{
ArrayList arr = new ArrayList();
arr.Add(0);
arr.Add(0);
arr.Add(0);
arr.Add(1);
arr.Add(0);
arr.Add(1);
arr.Add(1);
ArrayList res = findPartitions(arr);
for(int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find all possible
// max sum partitions
function findPartitions(A) {
let N = A.length, mx = 0;
// Prefix sum array
let sum = new Array(N + 1).fill(0), ans = [];
for (let i = 0; i < N; ++i)
sum[i + 1] = sum[i] + A[i];
// Find the partitions
// with maximum prefix sum
for (let i = 0; i <= N; ++i) {
// Calculate score for
// the current index
let score = i - sum[i]
+ sum[N] - sum[i];
// Compare current score
// with previous max
if (score > mx) {
ans = [i];
mx = score;
}
// If current score
// is greater than
// previous then push
// in the ans array.
else if (score == mx)
ans.push(i);
}
// Returning the resultant
// array of indices
return ans;
}
// Driver code
let res,
arr = [0, 0, 0, 1, 0, 1, 1];
res = findPartitions(arr);
for (let it of res)
document.write(it + " ");
// This code is contributed by Potta Lokesh
</script>
Producción
3 5
Complejidad temporal : O(N)
Espacio auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA