有一個包含（正數和負數）整數的數組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