Max Doppel-Summe slice

Wenn ich verstanden habe, das problem richtig, Sie wollen berechnen die maximale Summe subarray mit einem element fehlt.

Dein Algorithmus ist nicht für folgenden Fall:

 1 1 0 10 -100 10 0

In dem oben genannten Fall, der den Algorithmus identifiziert 1, 1, 0, 10 als die maximale Summe sub-array und lassen Sie sich 0 zu geben 12 als Ausgang. Sie können jedoch 1, 1, 0, 10, -100, 10 wie die Antwort nach dem Ausscheiden aus -100.

Können Sie mit einer modifizierten form der Kadane-Algorithmus berechnet die MAX Summe subarray Ende an jedem index.

1. Für jeden index, berechnen Sie die max_sum_ending_at[i] - Wert mithilfe der Kadane-Algorithmus in vorwärts-Richtung.
2. Für jeden index, berechnen Sie die max_sum_starting_from[i] - Wert mithilfe der Kadane-Algorithmus in umgekehrter Richtung.

3. Durchlaufen diese arrays gleichzeitig, und wählen Sie die 'Y', die den maximalen Wert von

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

Dies ist ein Java-100/100 Lösung:
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;

    }
}

Finden Sie weitere Informationen zu diesem Link zu Wikipedia und in der Programming Pearls Buch.

Ohne extra Speicher, 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;
}

Vb.net version der oben genannten Lösung ist wie folgt:

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

"Ergebnis anzeigen" auf codility

Hier ist eine alternative Lösung zu der vorgeschlagenen von mir vor, besser lesbar und verständlich:

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;

}

Hier 100% in python,
vielleicht nicht so elegant, wie einige der anderen oben genannten Lösungen, hält aber für alle Fälle ist möglich.

def solution(A):
#Trivial cases 
 if len(A)<=3:
  return 0 
 idx_min=A.index(min(A[1:len(A)-1]))
 minval=A[idx_min]
 maxval=max(A[1:len(A)-1])
 if maxval<0:
     return 0
 if minval==maxval:
     return minval*(len(A)-3)
#Regular max slice if all numbers > 0     
 if minval>=0:
  max_ending=0     
  max_slice=0
  for r in range(1,len(A)-1):
        if (r!=idx_min):     
         max_ending=max(0,A[r]+max_ending)
         max_slice = max(max_slice, max_ending)
  return max_slice  
#Else gets more complicated        
 else :
#First remove negative numbers at the beginning and at the end 
  idx_neg=1
  while A[idx_neg] <= 0 and idx_neg<len(A) :
   A[idx_neg]=0
   idx_neg+=1
  idx_neg=len(A)-2
  #<0 , 0
  while A[idx_neg] <= 0 and idx_neg > 0 :
   A[idx_neg]=0
   idx_neg-=1
#Compute partial positive sum from left
#and store it in Left array   
  Left=[0]*len(A) 
  max_left=0
  for r in range(1,len(A)-1):
      max_left=max(0,A[r]+max_left)
      Left[r]=max_left
#Compute partial positive sum from right
#and store it in Right array        
  max_right=0 
  Right=[0]*len(A)      
  for r in range(len(A)-2,0,-1):      
      max_right=max(0,A[r]+max_right)
      Right[r]=max_right   
#Compute max of Left[r]+Right[r+2].
#The hole in the middle corresponding
#to Y index of double slice (X, Y, Z)           
  max_slice=0
  for r in range(1,len(A)-3):
     max_slice=max(max_slice,Left[r]+Right[r+2])   
  return max_slice     
 pass