有一个包含（正数和负数）整数的数组A。查找（连续）子数组的元素绝对总和最小的，例如：找到子阵列的最小绝对总和
A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum
我已经通过实施蛮力算法，这是O(N^2)或O(N^3)开始，但它产生正确的结果。但任务规定：
complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)
一些搜索我想，也许Kadane的算法可以被修改，以适应这个问题，但我没能做到这一点之后。
我的问题是 - 卡丹的算法是否正确？如果不是的话，你能否指出我的方向是正确的（或者说一个能够帮助我的算法）？我不想要一个现成的代码，我只需要帮助找到正确的算法。
如果计算中的部分和 如
2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...
然后任何连续子阵列的总和是2的部分和的差。因此，要找到绝对值最小的连续子数组，我建议您对部分和进行排序，然后找到最接近的两个值，并使用原始序列中这两个部分和的位置来查找开始和结束的绝对值最小的子阵列。
这里的昂贵的一点是排序，所以我认为这运行在时间O(n * log(n))。
答案是肯定的，Kadane的算法绝对是解决您的问题的方法。
http://en.wikipedia.org/wiki/Maximum_subarray_problem
来源 - 我已经紧密地与一个博士生谁是整个博士论文是专门为最大子数列问题的工作。
我在Codility上做了这个测试，发现mcdowella的答案相当有帮助，但还不够我不得不说：所以这里是2015年的答案！我们需要建立数组A（这里称为P）的前缀和，例如：P [0] = 0，P [1] = P [0] + A [0]，P [2] = P [0,1] 1] + A [1]，...，P [N] = P [N-1] + A [N-1]
A的“min abs sum” P中的元素。因此，我们只需要.sort() P，并在每次使用2个连续元素时遍历它。这样我们有O（N + N log（N）+ N）等于O（Nlog（N））。
就是这样！
这是一个基于Kadane算法的C解决方案。 希望它有帮助。
#include <stdio.h>
int min(int a, int b)
{
return (a >= b)? b: a;
}
int min_slice(int A[], int N) {
if (N==0 || N>1000000)
return 0;
int minTillHere = A[0];
int minSoFar = A[0];
int i;
for(i = 1; i < N; i++){
minTillHere = min(A[i], minTillHere + A[i]);
minSoFar = min(minSoFar, minTillHere);
}
return minSoFar;
}
int main(){
int A[]={3, 2, -6, 4, 0}, N = 5;
//int A[]={3, 2, 6, 4, 0}, N = 5;
//int A[]={-4, -8, -3, -2, -4, -10}, N = 6;
printf("Minimum slice = %d \n", min_slice(A,N));
return 0;
}
这不能解决绝对的问题 – Paparazzi 2017-02-22 22:44:31
public static int solution(int[] A) {
int minTillHere = A[0];
int absMinTillHere = A[0];
int minSoFar = A[0];
int i;
for(i = 1; i < A.length; i++){
absMinTillHere = Math.min(Math.abs(A[i]),Math.abs(minTillHere + A[i]));
minTillHere = Math.min(A[i], minTillHere + A[i]);
minSoFar = Math.min(Math.abs(minSoFar), absMinTillHere);
}
return minSoFar;
}
这是C++实现Saksow的算法。
int solution(vector<int> &A) {
vector<int> P;
int min = 20000 ;
int dif = 0 ;
P.resize(A.size()+1);
P[0] = 0;
for(int i = 1 ; i < P.size(); i ++)
{
P[i] = P[i-1]+A[i-1];
}
sort(P.begin(),P.end());
for(int i = 1 ; i < P.size(); i++)
{
dif = P[i]-P[i-1];
if(dif<min)
{
min = dif;
}
}
return min;
}
def min_abs_subarray(a):
s = [a[0]]
for e in a[1:]:
s.append(s[-1] + e)
s = sorted(s)
min = abs(s[0])
t = s[0]
for x in s[1:]:
cur = abs(x)
min = cur if cur < min else min
cur = abs(t-x)
min = cur if cur < min else min
t = x
return min
您可以运行Kadane's algorithm两次（或做它一个GO）找到最小和最大的总和，其中发现在同样的最低作品最高与逆转迹象然后计算通过比较其绝对值来确定新的最大值
来源 - 有人（不记得是谁）在这个网站发表评论。
我不关注如何识别部分和的子数组。例如数组[-4,5，-1]有部分和[-4,1,0]，这似乎意味着子数组应该是[5，-1] = 4，而实际的解决方案是[-4,5，-1] = 0。 – Benubird 2015-06-11 12:55:29
我没有考虑整个阵列，被认为是一个子阵列。您可以分别考虑具有小部分和的子数组，或者在排序所有内容时确保包含具有零元素的子数组 - 这有一个零和，因此在您的示例中，您将得到部分和[-4， 1,0,0]，然后找出解决方案，该解决方案考虑到两个零和相加的项之间的跨度 - 整个阵列的开始和结束。从两个部分总和中识别出来的子阵列是部分总和中的项目集合，其中大部分项目相加但不在另一个项目中。 – mcdowella 2015-06-11 18:00:52
考虑3,3,3,4,5？也许我很困惑。 – Catalyst 2015-12-14 18:41:50