#include <stdio.h>
#include <stdlib.h>
struct ans {
int low, high, sum;
};
void FindMaxSub(int A[], int low, int high, struct ans *a);
void FindMaxCrosSub(int A[], int low, int mid, int high, struct ans *a);
int main()
{
int *A = NULL;
int B[17] = { 100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97 };
int n = 0, i = 0;
struct ans Ans;
scanf("%d", &n);
A = (int *)malloc(sizeof(int)*n);
for(i = 0; i<n; i++){
scanf("%d",A+i);
}
for (i = n - 1; i>0; i--) {
A[i] = A[i] - A[i - 1];
}
FindMaxSub(A, 1, n - 1, &Ans);
printf("
low = %d, high = %d, sum = %d
", Ans.low, Ans.high, Ans.sum);
system("pause");
return 0;
}
void FindMaxSub(int A[], int low, int high, struct ans *a)
{
if (low == high) {
a->low = a->high = low;
a->sum = A[low];
}
else {
struct ans a1, a2, a3;
int mid = (low + high) / 2;
FindMaxSub(A, low, mid, &a1);
FindMaxSub(A, mid + 1, high, &a2);
FindMaxCrosSub(A, low, mid, high, &a3);
if (a1.sum >= a2.sum && a1.sum >= a3.sum) {
a->low = a1.low;
a->high = a1.high;
a->sum = a1.sum;
}
else if (a2.sum >= a1.sum && a2.sum >= a3.sum) {
a->low = a2.low;
a->high = a2.high;
a->sum = a2.sum;
}
else {
a->low = a3.low;
a->high = a3.high;
a->sum = a3.sum;
}
}
}
void FindMaxCrosSub(int A[], int low, int mid, int high, struct ans *a)
{
int leftsum = A[mid], rightsum = A[mid + 1];
int minleft, i, maxright, j;
int sum = 0;
minleft = i = mid;
maxright = j = mid + 1;
while (i >= low) {
sum += A[i];
if (sum>leftsum) {
leftsum = sum;
minleft = i;
}
i--;
}
sum = 0;
while (j <= high) {
sum += A[j];
if (sum>rightsum) {
rightsum = sum;
maxright = j;
}
j++;
}
a->low = minleft;
a->high = maxright;
a->sum = (leftsum + rightsum);
}