有一个A包含（正负）整数的数组。找到一个（连续的）子数组，其元素的绝对和最小，例如：
A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum
我首先实现了一个蛮力算法，它是O(N^2)or O(N^3)，尽管它产生了正确的结果。但任务指定：
complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)
经过一番搜索，我认为也许可以修改 Kadane 的算法以适应这个问题，但我没有做到。
我的问题是 - Kadane 的算法是正确的方法吗？如果没有，您能否指出我正确的方向（或在这里命名一个可以帮助我的算法）？我不想要现成的代码，我只需要帮助找到正确的算法。
如果您计算部分总和
，例如
2, 2 +(-4), 2 + (-4) + 6, 2 + (-4) + 6 + (-3)...
那么任何连续子数组的和是两个部分和的差。所以要找到绝对值最小的连续子数组，我建议你对部分和进行排序，然后找到最接近的两个值，并使用这两个部分和在原始序列中的位置来找到开始和结束绝对值最小的子数组。
这里昂贵的一点是那种，所以我认为这是及时的O(n * log(n))。
这是 Saksow 算法的 C++ 实现。
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;
}
我在 Codility 上进行了这个测试，我发现 mcdowella 的答案很有帮助，但我不得不说的还不够：所以这是 2015 年的答案，伙计们！
我们需要构建数组 A（此处称为 P）的前缀和，例如：P[0] = 0, P[1] = P[0] + A[0], P[2] = P[1] + A [1], ..., P[N] = P[N-1] + A[N-1]
A 的“最小绝对和”将是 P 中 2 个元素之间的最小绝对差。所以我们只需要.sort()P 并循环遍历它，每次取 2 个连续的元素。这样我们就有 O(N + N log(N) + N) 等于 O(N log(N))。
而已！
答案是肯定的，Kadane 的算法绝对是解决您问题的方法。
http://en.wikipedia.org/wiki/Maximum_subarray_problem
资料来源——我与一位博士生密切合作，他的整个博士论文都致力于最大子阵列问题。
这是python中的迭代解决方案。这是 100% 正确的。
def solution(A):
memo = []
if not len(A):
return 0
for ind, val in enumerate(A):
if ind == 0:
memo.append([val, -1*val])
else:
newElem = []
for i in memo[ind - 1]:
newElem.append(i+val)
newElem.append(i-val)
memo.append(newElem)
return min(abs(n) for n in memo.pop())
您可以运行 Kadane's algorithm两次（或一次完成）以找到最小值和最大值总和，其中找到最小值的工作方式与使用反向符号的最大值相同，然后通过比较它们的绝对值来计算新的最大值。
来源——某人（不记得是谁）在本站发表的评论。
简短的甜美和工作就像一个魅力。JavaScript / NodeJs 解决方案
function solution(A, i=0, sum =0 ) {
//Edge case if Array is empty
if(A.length == 0) return 0;
// Base case. For last Array element , add and substart from sum
// and find min of their absolute value
if(A.length -1 === i){
return Math.min( Math.abs(sum + A[i]), Math.abs(sum - A[i])) ;
}
// Absolute value by adding the elem with the sum.
// And recusrively move to next elem
let plus = Math.abs(solution(A, i+1, sum+A[i]));
// Absolute value by substracting the elem from the sum
let minus = Math.abs(solution(A, i+1, sum-A[i]));
return Math.min(plus, minus);
}
console.log(solution([-100, 3, 2, 4]))
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
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;
}
这是一个基于 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;
}