Максимальная непрерывная подпоследовательность - динамическое программирование или жадный алгоритм?

Question

Учитывая массив vector<int> arr с положительными и отрицательными записями, задача максимального непрерывного подпоследовательности требует найти (смежный) отрезок массива arr с максимальной суммой. Сумма пустого сегмента равна нулю. Код C++ используемого алгоритма выглядит следующим образом:

int MaxContSum(const vector<int>& arr){ 
    int i,sum=0,max=0; 
    for(i=0;i<arr.size();i++){ 
     if(arr[i]>=0) {if(sum<0) sum=0;} 
     else {if(sum>max) max=sum;} 
     sum+=arr[i]; 
    } 
    if(sum>max) max=sum; return max; 
    } 

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

Answer 1

Это Kadane's algorithm for the maximum subarray problem. Он просматривает последовательность и отслеживает максимальную сумму субарама, найденную до этой итерации в целом, и максимальную сумму субарама, заканчивающуюся точно в этот момент. Как он знает начальную позицию подмассива, ведущую к лучшей сумме вплоть до этой точки? Всякий раз, когда 1) предыдущая сумма отрицательна, и 2) встречается положительный элемент, он начинает начинать с положительного элемента и продолжать оттуда. Доказательство того, что оно работает, - это простая индукция.

Этот алгоритм не жадный, но его можно рассматривать как динамическое программирование.

Жадный алгоритм делает локально-оптимальное предположение и придерживается его (просто продолжая его дальше и дальше). Здесь, наоборот, алгоритм может угадать, чтобы проверить подпоследовательность, начиная с некоторой точки (где сумма, заканчивающаяся на положительном элементе, отрицательна), а затем отбросить ее и попробовать подпоследовательность, начиная с какой-то другой точки (опять же, поскольку сумма становится отрицательной и элемент положителен).

И наоборот, его можно рассматривать как проблему динамического программирования. Поскольку запись Википедии ставит его:

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

Answer 2

два основных свойства, проблема должна быть для того, чтобы иметь право на получение решения с DP являются:

• Overlapping subproblems
• Optimal substructure

Из того, что вы представили, первое свойство, безусловно, не хватает и поэтому я бы не классифицировал этот алгоритм как DP. С другой стороны, вы используете результат вычисления для более мелкой задачи, чтобы получить окончательный результат, поэтому у нас есть Оптимальная субструктура, и это, вероятно, является причиной того, что вы нашли этот алгоритм в главе динамического программирования, хотя он не должен принадлежать там.