最大双切片总和
最近，我尝试解决codility中的Max Double Slice Sum问题，这是max slice问题的变体。 我的解决方案是在取出最小值时查找具有最大值的切片。 所以我实现了最大切片，但是在当前切片上取出了最小数量。
我的得分为61分，因为在一些测试中失败了，主要是arrays上的测试，包括负数和位置数。
你能帮我弄清楚代码失败的原因或者是否有更好的解决方案？
问题如下：
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. 我的代码如下：
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; } }
如果我已正确理解问题，则需要计算缺少一个元素的最大总和子数组。
您的算法不适用于以下情况：
1 1 0 10 -100 10 0
在上面的例子中，你的算法应该将1,1,0,10作为最大和子数组，并省略0给出12作为输出。 但是，在省略-100后，你可以得到1, 1, 0, 10, -100, 10作为答案。
您可以使用修改forms的Kadane算法来计算每个索引处结束的MAX Sum子arrays。
- 对于每个索引，通过在正向使用Kadane算法计算
max_sum_ending_at[i]值。 - 对于每个索引，通过反向使用Kadane算法计算
max_sum_starting_from[i]值。 -
同时迭代这些数组并选择具有最大值的’Y’
max_sum_ending_at [Y-1] + max_sum_starting_from [Y + 1]
您好此实现有100分
int i,n ; n = A.size(); if (3==n) return 0; vector max_sum_end(n,0); vector 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 int solution(vector &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和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; }
}
以上解决方案的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的结果
基于Abhishek Bansal解决方案的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;i0;n--){ max_start_at[n]=max(0,max_start_at[n+1]+A[n]); } for(let m=1;m
以下是我之前提出的替代解决方案，更具可读性和可理解性：
int solution(vector & A){ if(A.size() < 4 ) return 0; int maxSum = 0; int sumLeft = 0; unordered_map 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 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％，根据贪婪的要求。
#include #include #include using namespace std; int solution(vector &A) { unordered_map maxSliceLeftToRight; maxSliceLeftToRight[1] = 0; unordered_map 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; }