Максимизируйте точку, чтобы уменьшить массив, заменив подмассив его суммой

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

Примеры:

Input: N = 2, arr[] = {1, 5}
Output: 2
Explanation: Select subarray (0, 1). Then array arr[] become { 6 } and points earned = 2 * min(1, 5) = 2. Total points earned = 2

Input: N = 3, arr[] = {2, 3, 5}
Output: 14
Explanation: First select subarray (0, 1), then array arr[] become { 5, 5 } and points earned = 2 * min(2, 3) = 4. Select subarray (0, 1), then array arr[] become { 10 } and points earned = 2*  min(5, 5) = 10. Total points earned = 4 + 10 =14.

Подход с использованием суммы префиксов и DP (мемоизация):

The Basic idea to solve this problem statement is to maintain a prefix sum array and obtain sum between range using DP (memoization).

Let there be three elements in the subarray {a, b, c} with b > a > c.

1st Case: If we include all the element at a time. array becomes {a+b+c}, points reward = 3*min(a, b, c) = 3*c.

2nd Case: Now, take two element at a time, 
First select subarray(1, 2), array becomes (a, b+c), points reward = 2 * min(b, c) = 2*c
Now select subarray(0, 1), array becomes (a+b+c), points reward = 2 * min(a, b+c) = 2*a
Total points obtained = 2*c + 2*a 

Now, points obtained in the 2^nd case is more than points obtained in the first case as
a > c So 2*a > c. So it is optimal to not choose all of the three at a time and break it into two parts from b. This can be implemented with the help of dynamic programming to store the maximum possible point for a subarray [i, j] for avoiding repreated calculation.

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Создайте массив суммы префиксов pre[] , чтобы получить сумму между любым диапазоном за время O(1).
• Создайте рекурсивную функцию, которая принимает i и j в качестве параметров, определяющих диапазон группы.
  • Итерируйте от k = i до j , чтобы разделить заданный диапазон на две группы.
  • Вызовите рекурсивную функцию для этих групп.
    • Предположим, что ans1 и ans2 представляют общее количество баллов, полученных за левую и правую части соответственно.
    • Теперь для текущего раздела с индексом k потенциальным ответом будет ans1 + ans2 + 2* min(левый элемент, правый элемент), как видно из приведенного выше обсуждения.
  • Теперь левый элемент будет pre[k+1]-pre[i] , правый элемент будет pre[j-1] – pre[k+1] , который можно вычислить за время O(1) из суммы префикса множество.
• Максимальное значение, полученное для диапазона от 0 до N-1 , является требуемым ответом.

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в динамическое программирование — учебные пособия по структуре данных и алгоритмам
• Массив сумм префиксов — реализация и приложения в соревновательном программировании