最大双片总和 [英] Max Double Slice Sum
问题描述
最近，我试图解决codility的最大双片和问题是最大的问题片的一个变种。我的解决方法是找一个切片具有最大值时，其最小值被取出来。所以，我实现了最大片，但目前的片上拿出的最低数量。
我的分数是100 61，因为它在某些测试中失败了，主要是测试的阵列，包括消极和位置编号。
你能不能帮我弄清楚为什么code失败或者如果对于这个问题更好的解决方案？
的问题如下：
A非空零索引数组A由N个整数给出。
三元组（X，Y，Z）中，以使得0≤X - 其中; Y'LT; z，其中， N，被称为双片。
双片的总和（X，Y，Z）是A [X + 1] + A [X + 2 + ... + A总[Y - 1] + A [Y + 1] + A [ Y + 2 + ... + A [Z - 1]。
例如，数组A这样：
A [0] = 3
A [1] = 2
A [2] = 6
A [3] = -1
A [4] = 4
A [5] = 5
A [6] = -1
A [7] = 2
包含以下实施例双片：
双片（0，3,6），和是2 + 6 + 4 + 5 = 17，
双片（0，3,7），和是2 + 6 + 4 + 5 - 1 = 16，
双片（3，4，5），和是0。
的目标是找到任何双片的最大总和。
写一个函数：
一流的解决方案{公众诠释解决方案（INT [] A）; }
即，给定一个非空的零索引数组A由N个整数，返回任何双片的最大总和。
例如，给定：
A [0] = 3
A [1] = 2
A [2] = 6
A [3] = -1
A [4] = 4
A [5] = 5
A [6] = -1
A [7] = 2
函数应该返回17，因为数组A中没有双片具有大于17的总和。
假设：
N是在范围[3..100,000]内的整数。
数组A中的每个元素是在范围[-10,000..10,000]内的整数。
复杂：
预计最坏情况下的时间复杂度为O（N）;
预期的最坏情况的空间复杂度是O（N），超越输入存储（不计算所需的输入参数的存储）。
输入数组的元素可以被修改。
版权所有2009-2013通过Codility有限公司。版权所有。未经授权的复制，发表或披露禁止的。
和我的code是如下：
公共类解决方案{
公众诠释的解决方案（INT [] A）{
INT currentSliceTotal = 0;
整数currentMin = NULL，SliceTotalBeforeMin = 0;
INT maxSliceTotal = Integer.MIN_VALUE的;
的for（int i = 1; I＆LT;则为a.length-1;我++）{
如果（currentMin == NULL || A [1] - ; currentMin）{
如果（currentMin！= NULL）{
如果（SliceTotalBeforeMin + currentMin℃，）{
currentSliceTotal- = SliceTotalBeforeMin;
} 其他 {
currentSliceTotal + = currentMin;
}
}
currentMin = A [1];
SliceTotalBeforeMin = currentSliceTotal;
如果（SliceTotalBeforeMin℃，）{
SliceTotalBeforeMin = 0;
currentMin = NULL;
currentSliceTotal = 0;
}
} 其他 {
currentSliceTotal + = A [1];
}
maxSliceTotal = Math.max（maxSliceTotal，currentSliceTotal）;
}
返回maxSliceTotal;
}
}
如果我理解正确的问题，你要计算的最大总和子数组包含一个元素缺失。
您的算法，不得用于下列情况下工作：
1 1 0 10 -100 10 0
在上述情况下，你的算法应识别 1，1，0，10 作为最大总和子数组，并离开了 0 给 12 作为输出。但是，你可以有 1，1，0，10，-100，10 的离开了之后，答案 -100 。
您可以使用Kadane的算法来计算的总和MAX的改进形式子阵结束每一个索引处。
- 对于每一个指标，通过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]
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.
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.
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;
}
}
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, 10 as the maximum sum sub array and leave out 0 to give 12 as the output. However, you can have 1, 1, 0, 10, -100, 10 as the answer after leaving out -100.
You can use a modified form of Kadane's algorithm that calculates the MAX Sum subarray ending at each index.
- For each index, calculate the
max_sum_ending_at[i]value by using Kadane's algorithm in forward direction. - For each index, calculate the
max_sum_starting_from[i]value by using Kadane's algorithm in reverse direction. 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]
这篇关于最大双片总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
