Максимальная сумма подпоследовательности, при которой никакие три не идут подряд в пространстве O (1)

Учитывая массив A[] из N положительных чисел, задача состоит в том, чтобы найти максимальную сумму, которая может быть сформирована, если нет трех последовательных элементов.

Примеры:

Input: A[] = {1, 2, 3}, N=3
Output: 5
Explanation: Three of them can’t be taken together so answer is 2 + 3 = 5

Input: A[] = {3000, 2000, 1000, 3, 10}, N=5
Output: 5013

Здесь обсуждался подход O( N ), использующий вспомогательное пространство O(N) . Это может быть дополнительно оптимизировано с помощью следующего подхода, который занимает O (1) дополнительного пространства.

O(1) Космический подход: Из приведенного выше подхода мы можем сделать вывод, что для вычисления суммы [i] важны только значения суммы [i-1], суммы [i-2] и суммы [i-3] . Это наблюдение может помочь полностью отказаться от массива сумм и вместо этого просто сохранить некоторые переменные для решения проблемы, используя вспомогательное пространство O (1).

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте следующие переменные, которые будут использоваться:
  • сумма: здесь хранится окончательная сумма, так что никакие три элемента не являются последовательными.
  • first: здесь хранится сумма подпоследовательности до индекса i-1 .
  • second: здесь хранится сумма подпоследовательности до индекса i-2 .
  • третий: здесь хранится сумма подпоследовательности до индекса i-3 .
• Если N<3 , ответом будет сумма всех элементов, поскольку последовательных элементов не будет.
• В противном случае сделайте следующее:
  • Инициализировать третий с помощью A[0]
  • Инициализировать секунду с помощью A[0]+A[1]
  • Инициализировать сначала с помощью max(второй, A[1]+A[2])
  • Инициализируйте сумму с максимальным значением среди первых , вторых и третьих .
  • Итерируйте от 3 до N-1 и сделайте следующее для каждого текущего индекса i :
    • Возможны следующие три случая:
      • Исключить A[i], т.е. сумма = первая
      • Исключить A[i-1], т.е. сумма = секунда + A[i]
      • Исключить A[i-2] , т.е. сумма = третья + A[i] + A[i-1]
    • Таким образом, сумма обновляется как максимум между первым , (второй+A[i]) и (третьим+A[i]+A[i-1])
    • Обновите третье с помощью второго , второе с первым и первое с суммой .
• Наконец, верните sum .

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

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