Максимальная сумма, полученная при разделении массива на несколько подмассивов по заданным условиям

Учитывая массив arr[] размера N , задача состоит в том, чтобы вычислить максимальную сумму, которую можно получить, разделив массив на несколько подмассивов (возможно, один), где каждый подмассив, начинающийся с индекса i и заканчивающийся индексом j (j>= i) вносит вклад arr[j]-arr[i] в сумму.

Примеры:

Input: arr[]= {1, 5, 3}, N=3
Output: 
4
Explanation: The array can be divided into 2 subarrays:

• {1, 5} -> sum contributed by the subarray = 5-1 = 4
• {3} -> sum contributed by the subarray = 3-3 = 0

Therefore, the answer is 4.(It can be shown that there is no other way of dividing this array in multiple subarrays such that the answer is greater than 4).

Input: arr[] = {6, 2, 1}, N=3
Output:
0

Наивный подход: Наивный подход состоит в том, чтобы рассмотреть все возможные способы деления массива на 1 или более подмассивов и вычислить максимальную сумму, полученную для каждого.

Временная сложность: O(N* ^2N )
Вспомогательное пространство: O(1)

Наблюдение: Наблюдения, необходимые для решения проблемы, приведены ниже:

1. Массив должен быть разделен на несколько (возможно, один) подмассивов таким образом, чтобы каждый подмассив был самым длинным возрастающим подмассивом. Например, если arr[]={3,5,7,9,1} , оптимально рассматривать {3,5,7,9} как подмассив, поскольку он внесет вклад 9-3=6 в сумму. Дальнейшее разбиение уменьшает сумму, которая не является оптимальной.
2. Каждый элемент невозрастающего подмассива следует рассматривать как подмассив с одним элементом, чтобы они вносили 0 в сумму. В противном случае они будут вносить отрицательное значение. Например, если arr[i]>arr[i+1], оптимально рассматривать два подмассива длины 1, содержащие arr[i] и arr[i+1] по отдельности, чтобы они вносили (arr[i]- arr[i]) +(arr[i+1]-arr[i+1])=0 к ответу. Если бы они рассматривались вместе, они бы внесли вклад arr[i+1]-arr[i] , что является отрицательным числом, тем самым уменьшая сумму.

Эффективный подход: выполните следующие шаги, чтобы решить проблему:

1. Инициализировать переменную Sum значением 0.
2. Перейдите arr от 1 к N-1, используя переменную i , и сделайте следующее:
   1. Если arr[i]>arr[i-1] , добавьте arr[i]-arr[i-1] к Sum . Это работает, потому что сумма различий соседних элементов в отсортированном массиве равна разнице элементов на крайних концах. Здесь рассматриваются только возрастающие подмассивы как arr[i]>arr[i-1].

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)