How to solve this problem?

You are given an integer array A of size N. You can divide this array A into any number of contiguous subarrays (possibly zero). The degree of freedom for a subarray is the absolute difference between the maximum and minimum element in a subarray.

Task: Print the maximum sum of the degree of freedom of all subarrays that can be achieved by dividing A into some possible arrangement of contiguous subarrays


•A subarray of an array is a sequence obtained by removing zero or more elements from either both the front and back of the array. The subarrays of array [1,5,2] are ([1], [1,5] [1,5,2], [5], [5,2],[2]] and [1,2] cannot be called a subarray of [1,5,2] because it cannot be obtained by removing elements from front or back of [1,5,2] •Contiguous subarray means that all the subarrays should have consecutive indexes. An array [1,2,3] can be divided into contiguous subarray as [1,2,3]or [1,2],[3] or [1][2,3]


Assumptions N=5 A = [1,2,1,0,5]


Optimally we can divide A into three consecutive subarrays [1,2], [1] and [0,5]. The degree of freedoms of the subarrays is O and 5 respectively. Thus the maximum sum of the degree of freedom of all subarrays is 6.

A Represents an integer array denoting elements of array A

Test Cases: N=4; A=[1,4,2,3]; Output=4
N=5; A=[1,2,3,2,1]; Output=3