Максимальная сумма двойного среза

Здравствуйте эта реализация имеет 100 баллов

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 ;

Это решение Java 100/100: 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;

    }
}

Вы можете найти дополнительную информацию, перейдя по этой ссылкеWikipedia и в книгеProgramming Pearls .

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;
}

Без использования дополнительной памяти, 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;
}

Используя идею из http://en.wikipedia.org/wiki/Maximum_subarray_problem и ответ Абхишека Бансала выше. 100% прохождение теста:

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;
}

}

Vb.net версия вышеуказанного решения выглядит следующим образом:

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

Посмотреть результат на codility

Реализация JavaScript на основе решения Абхишек Бансал по.100/100 на 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;
}

Вот альтернативное решение, предложенное мной ранее, более читаемое и понятное:

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;

}

Ну, у меня есть мое решение, может быть, не самое лучшее один бит 100%/100%, согласно требованиям codility.

#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;
}