Java 最大双切片和

Max double slice sum

提问by Farid A

Recently, I tried to solve the Max Double Slice Sum problem in codility which is a variant of max slice problem. My Solution was to look for a slice that has maximum value when its minimum value is taken out. So I implemented max slice, but on the current slice took out the minimum number.

最近，我尝试解决 codility 中的 Max Double Slice Sum 问题，这是 max slice 问题的变体。我的解决方案是寻找一个在取出最小值时具有最大值的切片。所以我实现了最大切片，但在当前切片上取出了最小数量。

My score was 61 of 100 as it failed during some of the tests, mainly the tests on array including both negative and position numbers.

我的分数是 100 分中的 61 分，因为它在一些测试中失败了，主要是对数组的测试，包括负数和位置数。

Could you help me to figure out why the code failed or if there is a better solution for the problem?

你能帮我找出代码失败的原因，或者是否有更好的解决方案？

The problem is as follows:

问题如下：

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 2009–2013 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

And my code is as follows:

我的代码如下：

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

采纳答案by Abhishek Bansal

If I have understood the problem correctly, you want to calculate the maximum sum subarray with one element missing.

如果我正确理解了这个问题，您想计算缺少一个元素的最大和子数组。

Your algorithm shall not work for the following case:

您的算法不适用于以下情况：

 1 1 0 10 -100 10 0

In the above case, your algorithm shall identify 1, 1, 0, 10as the maximum sum sub array and leave out 0to give 12as the output. However, you can have 1, 1, 0, 10, -100, 10as the answer after leaving out -100.

在上述情况下，您的算法应识别1, 1, 0, 10为最大和子数组，并省略0给出12作为输出。但是，您可以1, 1, 0, 10, -100, 10在省略后作为答案-100。

You can use a modified form of Kadane's algorithm that calculates the MAX Sum subarray ending at each index.

您可以使用 Kadane 算法的修改形式来计算以每个索引结尾的 MAX Sum 子数组。

1. For each index, calculate the max_sum_ending_at[i]value by using Kadane's algorithm in forward direction.
2. For each index, calculate the max_sum_starting_from[i]value by using Kadane's algorithm in reverse direction.

3. Iterate these arrays simultaneously and choose the 'Y' that has the maximum value of

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

1. 对于每个指标，max_sum_ending_at[i]使用 Kadane 算法在正向计算值。
2. 对于每个指标，max_sum_starting_from[i]通过反向使用 Kadane 算法计算值。

3. 同时迭代这些数组并选择具有最大值的“Y”

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

回答by Guillermo

Hello this implementacion has 100 score

你好，这个实现有 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 ;

回答by Andrey Petrov

Using the idea from http://en.wikipedia.org/wiki/Maximum_subarray_problemand Abhishek Bansal's answer above. 100% test pass:

使用来自http://en.wikipedia.org/wiki/Maximum_subarray_problem和 Abhishek Bansal 的回答的想法。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;
}

}

}

回答by V Malhi

Vb.net version of the above solution is as below:

上述解决方案的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

View result on codility

查看有关 codility 的结果

回答by moxi

This is a Java 100/100 Solution: https://codility.com/demo/results/demoVUMMR9-JH3/

这是一个 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;

    }
}

You can find more information going to this Wikipedia linkand in the Programming Pearls book.

您可以在此Wikipedia 链接和Programming Pearls 书中找到更多信息。

回答by Joel Mitsui

C# solution 100/100

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

回答by Alexander Ivanenko

Without using extra memory, 100/100 C++:

不使用额外内存，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;
}

回答by terryc

Javascript implementation based on Abhishek Bansal's solution.100/100 on Codility.

基于 Abhishek Bansal 在 Codility 上的 solution.100/100 的 Javascript 实现。

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

回答by Andrushenko Alexander

Well, I have my solution, may be not the best one bit 100%/100%, according to codility requierments.

好吧，我有我的解决方案，根据 codility 要求，可能不是最好的 100%/100%。

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

回答by Andrushenko Alexander

Here is an alternative solution to the proposed by me before, more readable and understandable:

这是我之前提出的替代解决方案，更具可读性和可理解性：

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;

}

}