최대 배열 변수의 합계 사이의 절대 차이

Question

N 개의 숫자가 있습니다. A [0], A [1], A는 [2], a는 [3], ...., A [N]

두 단계가있다 : -

단계 1 -을 찾을 [i]에서 a [j]까지 배열에있는 요소들의 합.

단계 2 : [m]에서 [n]까지 배열의 요소 합계를 찾습니다.

1 난 10000

-10^9 <는 [N] < = 10^9 =

2 ≤ N ≤ J <미터 ≤ n 개의 ≤에 N.에게 ≤ ≤.

두 개의 단계에서 얻은 값의 절대 차이로 결정되는 총 값을 계산해야하며이 총 값을 최대화해야합니다. 예 용

,

N 내가 최대 총 값을 따라서 얻어진 = 1, J = 2, K = 3, L = 4 4
1 1 -1 -1

이다 = | ((-1) + (-1)) - (1 + 1) | = 4.

이것은 내가 slove하려고하는 질문이며, 나는 초보자입니다. 나는이 질문을 해결하는 방법을 모릅니다. 사용하고자하는 알고리즘을 알려주세요. 어떻게 i, j, m 및 n을 찾을 수 있습니까? 조건.

Answer 1

-10^9 < = a [N] < = 10^9 float, 의 정확도가 손실되지 않도록 힙을 사용하십시오..

힙과 연산이 무엇인지 모르는 경우 대부분의 알고리즘 서적과 웹에서 찾을 수 있습니다. 여기

는 의사 코드, 그리고 난 내가, J는, m은 n을 주어 가정 : 나는, 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]; 

, 인, 파티션에 의해 그들을 발견 빠른 정렬의 일반적인 부분. 예를

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.