Maximum Subarray Difference

Given an array of integers of size \(N\), your task is to determine the maximum difference value among all contiguous subarrays of the array. For a subarray \(A[i \dots j]\), the difference is defined as:

\(\max(A[i \dots j]) - \min(A[i \dots j])\)

It can be observed that the maximum difference value is achieved by finding the overall maximum and minimum values in the array (since there always exists a contiguous subarray including both). If the array contains all identical elements, the answer will be 0.

inputFormat

The input consists of two lines:

• The first line contains an integer \(N\), representing the number of elements in the array.
• The second line contains \(N\) space-separated integers denoting the elements of the array.

outputFormat

Output a single integer, which is the maximum difference value among all contiguous subarrays of the given array.

5
1 3 2 7 9

8