algo.cc

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <iterator>

using namespace std;

int abs(int x) {
        return x > 0 ? x : -x;
}

int solution(int* A, int N) {
        int left[N];
        int right[N];

        memset(left, 0, sizeof(int) * N);
        memset(right, 0, sizeof(int) * N);

        left[0] = A[0];
        for(int i = 1; i < N; ++i) {
                if(A[i] > left[i - 1]) {
                        left[i] = A[i];
                } else {
                        left[i] = left[i - 1];
                }
        }

//      copy(left, left + N, ostream_iterator<int>(cout, "\t"));
//      printf("\n");

        right[N - 1] = A[N - 1];
        for(int i = N - 2; i >= 0; --i) {
                if(A[i] > right[i + 1]) {
                        right[i] = A[i];
                }else {
                        right[i] = right[i + 1];
                }
        }

        int max = 0;

        for(int i = 0; i < N - 1; ++i) {
                int cur = abs(left[i] - right[i + 1]);
                if(cur > max) {
                        max = cur;
                }
        }

        return max;
}

int main() {
        int A[] = {1,3, -3 };
        int res = solution(A, sizeof(A)/sizeof(int));
        printf("%d\n", res);

        int B[] = {4,3,2,5,1,1};
        res = solution(B, sizeof(B)/sizeof(int));
        printf("%d\n", res);
        return 0;
}