-5

有N个数字。a[0],a[1],a[2],a[3],....,a[N]

有两个阶段：-

阶段 1：- 求数组中从 a[i] 到 a[j] 的元素之和。

阶段 2：- 求数组中从 a[m] 到 a[n] 的元素之和。

1 ≤ i ≤ j < m ≤ n ≤ N。

2≤N≤10000

-10^9 <= a[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。

4

1 回答 1

0

因为 -10^9 <= a[N] <= 10^9 in float，使用堆来避免精度损失。

如果您不知道什么是堆及其操作，您可以在大多数算法书籍和网络上找到它们。

这是伪代码，我想 i,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.
于 2013-06-13T03:26:57.783 回答