最大數組變量之和的絕對差值

Question

有N個數字。 一個[0]，A [1]，A [2]，[3]，...，一個[N]

有兩個階段： -

1階段： - 查找從[i]到[j]數組中元素的總和。

階段2： - 從[m]到[n]找到數組中元素的總和。

1≤I≤Ĵ<米≤N≤N.

2≤N≤10000

-10^9 < =α[N] < = 10^9。

我必須計算其總值由兩個階段中獲得的值之間的絕對差值確定，並且該總值應該最大化。

爲例如

N = 4
1 1 -1 -1

I = 1，因此，所獲得的最大總值j = 2，K = 3，L = 4 是| （（-1）+（-1）） - （1 + 1）| = 4。

這是我試圖解決的問題，我是一個新手，我不知道如何解決這個問題，請指導我使用哪種算法。如何找到i，j，m和n條件。

Answer 1

as -10^9 < = a [N] < = 10^9浮點數，使用堆來避免丟失精度。

如果你不知道什麼是堆及其操作，你可以在大多數算法書籍和網頁上找到它們。

這裏是僞代碼，我認爲我，J，M，給出了N：

build a[i...j] to a max-heap heap1; 
build a[m...n] to a min-heap heap2; 
size1 = j-i+1; 
size2 = n-m+1; 
while(size1>1) { 
    n1 = extractmax(); 
    n2 = extractmax(); 
    temp = n1+n2; 
    insert(heap1,temp) 
} 
//do the same thing to heap2,but use extractmin() instead of extractmax() 

result = abs(a[i])+a[m]; 

如果I，J，M，N不給，由分區找到他們，這是快速排序的典型部分。

例如

a[0] = 0; 
i=j=0;//a[0] is useless, and 1 ≤ i ≤ j < m ≤ n ≤ N 
m=n=N; 
if(a[N]<=0) 
    temp = a[N]; 
a[N] = -1; 
//pre: a[i...j] is non-positive 
     a[m...n] is non-negetive 

while(j<=m+1){ 
    while(a[j+1]<=0) 
     j++; 
    while(a[m-1]>=0) 
     m--; 
    if(j+1>m) 
     break; 
    swap(a[j+1],a[m-1]); 
    j++;m--; 
} 
if(temp<=0) { //insert a[N] back 
    a[N] = a[m]; 
    a[m] = temp; 
    j = m; 
    m++; 
} 

//then you will have checked all elements 
//and make sure that non-positive elements are consecutive 
//so as to non-negative elements 
//now you have i,j,m,n to run pseudo-code at the beginning. 
//although i,j may be not more than 0,it depends on the data in your array.