Подпоследовательность максимальной суммы любого размера, попеременно возрастающая-убывающая

Опубликовано: 20 Сентября, 2022

Учитывая массив целых чисел arr[] , найдите подпоследовательность с максимальной суммой , элементы которой сначала уменьшаются, затем увеличиваются или наоборот. Подпоследовательность может начинаться в любом месте основной последовательности, не обязательно с первого элемента основной последовательности.

A sequence {x1, x2, .. xn} is an alternating sequence if its elements satisfy one of the following relations (As described in the article Longest alternating subsequence): 

Two adjacent elements that are equal are not counted as alternating.

x1 < x2 > x3 < x4 > x5 < …. xn 
or 
x1 > x2 < x3 > x4 < x5 > …. xn

Примеры :

Input: arr[] = {4, 8, 2, 5, 6, 8}
Output: 26
Explanation: Alternating subsequence with maximum sum is {4, 8, 6, 8}. Sum = 4 + 8 + 6 + 8 = 26

Input: arr[] = {0, 1, 1, 1, 3, 2, 5}
Output: 11
Explanation: Alternating subsequence with maximum sum is {1, 3, 2, 5}. Sum = 1 + 3 + 2 + 5 = 11

Input: arr[] = {1, 4, 5}
Output: 9
Explanation: Alternating subsequence with maximum sum is {4, 5}. Sum = 4 + 5 = 9

Input: arr[] = {1, 0, 1, 0, 0, 3}
Output: 5
Explanation: Alternating subsequence with maximum sum is {1, 0, 1, 0, 3}. Sum = 1 + 0 + 1 + 0 + 3 = 5

Input: arr[] = {5, 5}
Output: 5
Explanation: Alternating subsequence with maximum sum is {5}. Sum = 5

Эта задача является расширением задачи о чередующейся подпоследовательности максимальной суммы. В отличие от предыдущей задачи, теперь нам нужно вычислить максимальную сумму чередующейся подпоследовательности вне зависимости от того, где она находится в основной последовательности , и независимо от того, начинается ли она с двух элементов по возрастанию или с двух элементов по убыванию .

Подход: Эта проблема может быть решена с помощью динамического программирования в сочетании с возвратом . Предположим, у нас есть массив arr[] с любыми N элементами.

  • Мы можем рассматривать каждый элемент arr[i] как завершающий элемент чередующейся последовательности.
  • Может быть много чередующихся подпоследовательностей, последним элементом которых является arr[i] , но наверняка одна из них является последовательностью с наибольшей суммой.
  • Кроме того, максимальная сумма чередующихся подпоследовательностей, оканчивающихся на arr[i] , не обязательно больше , чем максимальная сумма чередующихся подпоследовательностей, заканчивающихся на arr[i-1]. И это основа для реализации алгоритма по технике Backtracking.
  • Создайте массив, скажем, maxSum[] длины N , в котором будут храниться все максимальные суммы, заканчивающиеся на каждом элементе массива arr[] . В частности, maxSum[i] будет хранить максимальную сумму чередующейся подпоследовательности, заканчивающейся значением arr[i].
  • Мы будем использовать другой массив before[] для хранения значения, предшествующего последнему элементу каждой чередующейся подпоследовательности с максимальной суммой.

For example, an array arr[] = {1, 5, 7, 3, 4, 5} will have an alternating subsequence {5, 7, 3, 4} whose maximum sum is 5 + 7 + 3 + 4 = 19. 
The subsequence {5, 7, 3, 4} ends at the value 4, which has index 4 in the array arr[]. 
So we have arr[4] = 4, maxSum[4] = 19,  before[4] = 3 (because arr[3] = 3). 
Those values ​​will be calculated and saved into two arrays maxSum[] and before[] during the calculation and can be reused as needed.

Используйте следующие шаги для реализации подхода:

  • Используйте цикл для перебора каждого элемента массива arr[]. Каждый раз, когда мы проходим через элемент arr[i], мы смотрим на предшествующие ему элементы:

i Loop traversal from 1 to N-1 (There’s no need to start at position 0, because that’s the base case):
        j Loop traversal from 0 to i-1:

  • В каждом состоянии i и j мы будем повторно использовать любую maxSum[j] с 0 <= j < i в соответствии с принципом динамического программирования:

if:
        (arr[i] > arr[j] && arr[before[j]] > arr[j]) 
                            or
        (arr[i] < arr[j] && arr[before[j]] < arr[j])

then:
        sum = arr[i] + maxSum[j] 

  • Если maxSum[j] не удовлетворяет вышеуказанному условию, это могут быть два равных элемента . Поскольку два одинаковых элемента не рассматриваются как чередующаяся последовательность, мы берем только один из них.

if: 
        arr[i] == arr[j]

then:
        sum = maxSum[j]

  • Или это может быть не что-то из вышеперечисленного, например наличие более двух элементов в порядке возрастания или наличие более двух элементов в порядке убывания.

Example {1, 5, 7, 3, 4, 5}. Suppose we are at i = 5, j = 4. 

  • Then before[4] is the 3-rd element, and (arr[before[j]], arr[j], arr[i]) = (arr[before[4]], arr[4], arr[5]) = (arr[3], arr[4], arr[5]) = (3, 4, 5).
  • The above one is not a valid alternating subsequence, meaning that before[j] is not the index of a valid value.
  • We will look at the preceding element of arr[before[j]] in its alternating sequence: before[before[j]] = before[3] = 2, and arr[2] with arr[4] and arr[5] form a valid subsequence (7, 4, 5).
  • So we get a value of arr[5] + arr[4] + maxSum[2], which is the final sum of state {i = 5, j = 4}.
  • We need to compare it with other {i and j} states (like {i = 5, j = 3}, {i = 5, j = 2}…) to get the final result for maxSum[5].
  • Then save j into the before[5] if it precedes arr[5] and helps arr[5] form a valid subsequence with a maximum sum at state 5.

Взгляните на иллюстрацию ниже, чтобы понять идею.

index      :   0  1  2  3  4  5  || N = 6
arr[]      :   1, 5, 7, 3, 4, 5

—————————————————————————————————-

maxSum[0]  :   1  0  0  0  0  0   = 1 base case
before[-1] :  -1  _  _  _  _  _

maxSum[1]  :   1  6  0  0  0  0   = 6 because 1 + 5
before[1]  :  -1  0  _  _  _  _

maxSum[2]  :   1  6 12  0  0  0   = 12 because 1, 5, 7 isn’t alternating subsequence, and just 5 & 7 
before[2]  :  -1  0  1  _  _  _    is valid, we use backtracking at index 2 so 
we will go through the following subsequence: {1, 7}, {5, 7}. We have {5, 7} because before[1] is index 0, 
we continue to find value at before[before[1]] = -1, whose value is 0, so 0 + 5 + 7 = 12 > 1 + 7.

maxSum[3]  :   1  6 12 15  0  0   = 15 because 5, 7, 3 is valid alternating subsequence, 
before[3]  :  -1  0  1  2  _  _ so 3 + max(maxSum[2], maxSum[1], maxSum[0]) = 3 + 12.

maxSum[4]  :   1  6 12 15 19  0  = 19 because 5, 7, 3, 4 is valid alternating subsequence,
before[4]  :  -1  0  1  2  3  _   so 4 + max(maxSum[3], maxSum[2],… maxSum[0]) = 4 + 15.

maxSum[5]  :   1  6 12 15 19 21   = 21, arr[5] cannot be the next element of maxSum[4] because 3, 4, 5
before[5]  :  -1  0  1  2  3  2 isn’t alternating subsequence. So we need use backtracking here. 
We will treat the value 3 as an invalid value for the alternating subsequence ending in arr[5]. 
We need to find the preceding element of before[arr[4]] in the sum of maxSum[4] recursively, 
that is index 2. Now 7, 4, 5 have formed a valid alternating subsequence. 
So we have 5 + max(backtracking(index 4), maxSum[3], maxSum[2],…) = 5 + 16 ( because 4 + 7 + 5)
Then, final max sum of alternating subsequence of arr is max element of “maxSum” array.

Output: 21

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

Временная сложность : O(N 2 ), где N — длина массива.
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ