Max doble rebanada suma

Recientemente, traté de resolver el Max Doble Rebanada Suma problema en codility que es una variante de max rebanada problema. Mi Solución fue buscar un sector que tiene valor máximo cuando su valor mínimo es llevado a cabo. Por lo que he implementado max sector, pero en la actual rebanada se llevó a cabo el número mínimo.

Mi puntaje fue de 61 de 100 por lo que no pudo durante algunas de las pruebas, principalmente las pruebas en la matriz que incluye tanto la negativa como la posición de los números.

Me podrían ayudar a entender por qué el código de error o si hay una mejor solución para el problema?

El problema es el siguiente:

A non-empty zero-indexed array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0  X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + ... + A[Y  1]+ A[Y + 1] + A[Y + 2] + ... + A[Z  1].
For example, array A such that:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
contains the following example double slices:
double slice (0, 3, 6), sum is 2 + 6 + 4 + 5 = 17,
double slice (0, 3, 7), sum is 2 + 6 + 4 + 5  1 = 16,
double slice (3, 4, 5), sum is 0.
The goal is to find the maximal sum of any double slice.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty zero-indexed array A consisting of N integers, returns the maximal sum of any double slice.
For example, given:
A[0] = 3
A[1] = 2
A[2] = 6
A[3] = -1
A[4] = 4
A[5] = 5
A[6] = -1
A[7] = 2
the function should return 17, because no double slice of array A has a sum of greater than 17.
Assume that:
N is an integer within the range [3..100,000];
each element of array A is an integer within the range [−10,000..10,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the    storage required for input arguments).
Elements of input arrays can be modified.
Copyright 20092013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

Y mi código es el siguiente:

public class Solution {
public int solution(int[] A) {
int currentSliceTotal=0; 
Integer currentMin=null, SliceTotalBeforeMin =0;
int maxSliceTotal= Integer.MIN_VALUE;
for(int i= 1; i<A.length-1; i++){
if( currentMin==null || A[i] < currentMin ){
if(currentMin!=null ){
if(SliceTotalBeforeMin+currentMin <0){
currentSliceTotal-=SliceTotalBeforeMin;
} else {
currentSliceTotal += currentMin;
}
}                
currentMin = A[i];
SliceTotalBeforeMin  =currentSliceTotal;
if( SliceTotalBeforeMin<0){
SliceTotalBeforeMin = 0;
currentMin = null;
currentSliceTotal = 0;
}
} else {
currentSliceTotal+= A[i];
}
maxSliceTotal = Math.max(maxSliceTotal, currentSliceTotal);
}
return maxSliceTotal;
}
}

OriginalEl autor Farid A | 2013-12-18

10 respuestas

  1. 20

    Si he entendido el problema correctamente, se desea calcular la suma máxima subarray con uno de los elementos que faltan.

    Su algoritmo no podrá trabajar para el siguiente caso:

     1 1 0 10 -100 10 0

    En el caso anterior, el algoritmo deberá identificar 1, 1, 0, 10 como el máximo de la suma de la sub matriz y dejar fuera 0 para dar 12 como la salida. Sin embargo, usted puede tener 1, 1, 0, 10, -100, 10 como la respuesta después de salir fuera -100.

    Puede utilizar una forma modificada de la Kadane del algoritmo que calcula el máximo de la Suma de la subarray terminando en cada índice.

    1. Para cada índice, se calcula la max_sum_ending_at[i] valor mediante Kadane del algoritmo en la dirección de avance.
    2. Para cada índice, se calcula la max_sum_starting_from[i] valor mediante Kadane del algoritmo en dirección inversa.
    3. Recorrer estas matrices simultáneamente y elegir la ‘Y’ que tiene el valor máximo de

      max_sum_ending_at[Y-1] + max_sum_starting_from[Y+1]

    Gracias Abhishek. Que es una elegante solución para el problema.
    Brillante solución, Abhishek. La búsqueda de una “Y” valor por encontrar el índice que maximiza la suma de los max secuencias a su derecha e izquierda.
    Gracias.. 🙂
    Simple, elegante y de trabajo, THX 😉
    Ok.. para { 3, 2, 6, -1, -1, 4, 5, -1, 2 } esto devolverá 16 no 17… ¿está bien? Donde se dijo en la tarea de establecer que la distancia entre las rebanadas deben ser de 1?? Ok… lo siento, ahora a ver a (0, 3, 6) significa 0-3 3-6.. hmm tal especulativo de la tarea.

    OriginalEl autor Abhishek Bansal

  2. 6

    Hola esta implementacion 100 de la puntuación

    int i,n ;
    n = A.size();
    if (3==n) return 0;
    vector<int>  max_sum_end(n,0);
    vector<int>  max_sum_start(n,0);
    for (i=1; i< (n-1); i++) //i=0 and i=n-1 are not used because x=0,z=n-1
    {
    max_sum_end[i]   = max ( 0 , max_sum_end[i-1] + A[i]  ); 
    }
    for (i=n-2; i > 0; i--) //i=0 and i=n-1 are not used because x=0,z=n-1
    {
    max_sum_start[i]   = max ( 0 , max_sum_start[i+1] + A[i]  ); 
    }  
    int maxvalue,temp;
    maxvalue = 0;
    for (i=1; i< (n-1); i++)
    {
    temp = max_sum_end[i-1]  + max_sum_start[i+1];
    if ( temp >  maxvalue) maxvalue=temp;
    }
    return maxvalue ;
    Creo que esto no funciona si la matriz sólo tiene valores negativos. Teniendo en cuenta que el 2 subarrays debe tener al menos un elemento, no se puede simplemente establecer max_sum a cero.
    Los dos subarrays puede ser 0. Ver double slice (3, 4, 5), sum is 0. en la pregunta.

    OriginalEl autor Guillermo

  3. 2

    Este es un Java 100/100 Solución:
    https://codility.com/demo/results/demoVUMMR9-JH3/

    class Solution {
    public int solution(int[] A) {        
    int[] maxStartingHere = new int[A.length];
    int[] maxEndingHere = new int[A.length];
    int maxSum = 0, len = A.length;
    for(int i = len - 2; i > 0; --i ) {            
    maxSum = Math.max(0, A[i] + maxSum);
    maxStartingHere[i] = maxSum;
    }
    maxSum = 0;
    for(int i = 1; i < len - 1; ++i ) {            
    maxSum = Math.max(0, A[i] + maxSum);
    maxEndingHere[i] = maxSum;
    }
    int maxDoubleSlice = 0;
    for(int i = 0; i < len - 2; ++i) {
    maxDoubleSlice = Math.max(maxDoubleSlice, maxEndingHere[i] + maxStartingHere[i+2]);
    }
    return maxDoubleSlice;
    }
    }

    Usted puede encontrar más información ir a este Enlace de Wikipedia y en el Programación de Perlas libro.

    OriginalEl autor moxi

  4. 1

    Solución de C# 100/100

    public int solution(int[] A) {
    int[] forw = new int[A.Length];
    int[] rewi = new int[A.Length];
    bool isAllNeg = true;
    for (int i = 1; i < A.Length; i++)
    {
    forw[i] = Math.Max(0, forw[i - 1] + A[i]);
    if (A[i] > 0 && isAllNeg) isAllNeg = false;
    }
    if (isAllNeg)
    return 0;
    for (int i = A.Length - 2; i >= 0; i--)
    {
    rewi[i] = Math.Max(0, rewi[i + 1] + A[i]);
    }
    int maxsum = 0;
    for (int i = 1; i < A.Length - 1; i++)
    {
    maxsum = Math.Max(maxsum, forw[i - 1] + rewi[i + 1]);
    }
    return maxsum;
    }

    OriginalEl autor Joel Mitsui

  5. 1

    Sin el uso de memoria extra, 100/100 C++:

    #include <algorithm>
    int solution(vector<int> &A) {
    int max_slice = 0;
    int max_slice_i = 0;
    int min_val = 0;
    int mss = 0;
    int mse = 0;
    int s = 1;
    int msmv = 0;
    int max_slice_i_orig = 0;
    int os = 1;
    for(size_t i = 1;i < A.size() - 1;i++)
    {
    int v = max_slice_i;
    if(max_slice_i > 0 && A[i] < 0)
    {
    if(A[i] < min_val)
    {
    v = max_slice_i_orig;
    s = os;
    min_val = std::max(A[i], -max_slice_i_orig); 
    } else
    {
    v = max_slice_i + A[i];               
    }                        
    } else
    {
    v = max_slice_i + A[i];
    }
    int new_orig_v = max_slice_i_orig + A[i];
    if(new_orig_v < 0)
    {
    max_slice_i_orig = 0;
    os = i + 1;
    } else
    {
    max_slice_i_orig = new_orig_v;
    }
    if(v > 0)
    {                    
    max_slice_i = v;                                   
    } else {            
    max_slice_i = 0;
    min_val = 0;
    s = i + 1;
    }
    if(max_slice_i > max_slice)        
    {
    mss = s;
    mse = i;
    msmv = min_val;
    max_slice = max_slice_i;
    }
    }
    //if all are positive
    if(msmv == 0)
    {
    if(mss == 1 && mse == A.size() - 2)
    {
    int min = 10001;
    for(int j = mss;j <= mse;j++)
    {
    if(A[j] < min)
    min = A[j];
    }
    max_slice -= min;
    }
    }
    return max_slice;
    }

    OriginalEl autor Alexander Ivanenko

  6. 0

    Con la idea de http://en.wikipedia.org/wiki/Maximum_subarray_problem
    y Abhishek Bansal la respuesta anterior. 100% de prueba:

    public class Solution {
    public int solution(int[] A) {
    int[] maxEndingHere = maxEndingHere(A);
    int[] maxStartingHere = maxStartingHere(A);
    int maxSlice = 0;
    for (int i = 1; i < A.length-1;i++) {
    maxSlice = Math.max(maxSlice, maxEndingHere[i-1]+maxStartingHere[i+1]);
    }
    return maxSlice;
    }
    /**
    * Precalculate ending subarrays. Take into account that first and last element are always 0
    * @param input
    * @return
    */
    public static int[] maxEndingHere(int[] input) {
    int[] result = new int[input.length];
    result[0] = result[input.length-1] = 0;
    for (int i = 1; i < input.length-1; i++) {
    result[i] = Math.max(0, result[i-1] + input[i]);
    }
    return result;
    }
    /**
    * Precalculate starting subarrays. Take into account that first and last element are always 0
    * @param input
    * @return
    */
    public static int[] maxStartingHere(int[] input) {
    int[] result = new int[input.length];
    result[0] = result[input.length-1] = 0;
    for (int i = input.length-2; i >= 1; i--) {
    result[i] = Math.max(0, result[i+1] + input[i]);
    }
    return result;
    }

    }

    OriginalEl autor Andrey Petrov

  7. 0

    Vb.net versión de la solución anterior es la siguiente:

    Private Function solution(A As Integer()) As Integer
    ' write your code in VB.NET 4.0
    Dim Slice1() As Integer = Ending(A)
    Dim slice2() As Integer = Starting(A)
    Dim maxSUM As Integer = 0
    For i As Integer = 1 To A.Length - 2
    maxSUM = Math.Max(maxSUM, Slice1(i - 1) + slice2(i + 1))
    Next
    Return maxSUM
    End Function
    Public Shared Function Ending(input() As Integer) As Integer()
    Dim result As Integer() = New Integer(input.Length - 1) {}
    result(0) = InlineAssignHelper(result(input.Length - 1), 0)
    For i As Integer = 1 To input.Length - 2
    result(i) = Math.Max(0, result(i - 1) + input(i))
    Next
    Return result
    End Function
    Public Shared Function Starting(input() As Integer) As Integer()
    Dim result As Integer() = New Integer(input.Length - 1) {}
    result(0) = InlineAssignHelper(result(input.Length - 1), 0)
    For i As Integer = input.Length - 2 To 1 Step -1
    result(i) = Math.Max(0, result(i + 1) + input(i))
    Next
    Return result
    End Function
    Private Shared Function InlineAssignHelper(Of T)(ByRef target As T, value As T) As T
    target = value
    Return value
    End Function

    Resultados de la vista en codility

    OriginalEl autor V Malhi

  8. 0

    Javascript aplicación basada en Abhishek Bansal de la solución.100/100 en Codility.

    function solution(A) {
    let maxsum=0;
    let max_end_at=Array(A.length);
    let max_start_at=Array(A.length);
    max_end_at[0]=max_start_at[A.length-1]=max_end_at[A.length-1]=max_start_at[0]=0;
    let {max}=Math;
    for(let i=1;i<A.length-1;i++){
    max_end_at[i]=max(0,max_end_at[i-1]+A[i]);
    }
    for(let n=A.length-2;n>0;n--){
    max_start_at[n]=max(0,max_start_at[n+1]+A[n]);
    }
    for(let m=1;m<A.length-1;m++){
    maxsum=max(maxsum,max_end_at[m-1]+max_start_at[m+1]);
    }
    return maxsum;
    }

    OriginalEl autor terryc

  9. 0

    Aquí es una solución alternativa a la propuesta por mí antes de que, más legible y comprensible:

    int solution(vector<int> & A){
    if(A.size() < 4 )
    return 0;
    int maxSum = 0;
    int sumLeft = 0;
    unordered_map<int, int> leftSums;
    leftSums[0] = 0;
    for(int i = 2; i < A.size()-1; i++){
    sumLeft += A[i-1];
    if(sumLeft < 0)
    sumLeft = 0;
    leftSums[i-1] =  sumLeft;
    }
    int sumRight = 0;
    unordered_map<int, int> rightSums;
    rightSums[A.size()-1] =  sumRight;
    for( int i = A.size() - 3; i >= 1; i--){
    sumRight += A[i+1];
    if(sumRight < 0)
    sumRight = 0;
    rightSums[i+1] = sumRight;
    }
    for(long i = 1; i < A.size() - 1; i++){
    if(leftSums[i-1] + rightSums[i+1] > maxSum)
    maxSum = leftSums[i-1] + rightSums[i+1];
    }
    return maxSum;

    }

    OriginalEl autor Andrushenko Alexander

  10. 0

    Bueno, tengo mi solución, puede no ser la mejor bits 100%/100%, de acuerdo a codility requierments.

    #include<vector>
    #include<unordered_map>
    #include<algorithm>
    using namespace std;
    int solution(vector<int> &A) {
    unordered_map<size_t, int> maxSliceLeftToRight;
    maxSliceLeftToRight[1] = 0;
    unordered_map<size_t, int> maxSliceRightToLeft;
    maxSliceRightToLeft[A.size() - 2] = 0;
    int sum = 0;
    for (size_t i = 2; i < A.size() - 1; i++) {
    int tmpSum = max(sum + A[i - 1], 0);
    sum = max(A[i - 1], tmpSum);
    maxSliceLeftToRight[i] = sum;
    }
    sum = 0;
    for (size_t i = A.size() - 3; i > 0; i--) {
    int tmpSum = max(sum + A[i + 1], 0);
    sum = max(A[i + 1], tmpSum);
    maxSliceRightToLeft[i] = sum;
    }
    int maxDoubleSliceSum = 0;
    for (auto & entry : maxSliceLeftToRight) {
    int maxRight = maxSliceRightToLeft[entry.first];
    if (entry.second + maxRight > maxDoubleSliceSum)
    maxDoubleSliceSum = entry.second + maxRight;
    }
    return maxDoubleSliceSum;
    }

    OriginalEl autor Andrushenko Alexander

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *