Наибольшая сумма подпоследовательности

Question

Дана последовательность натуральных цифр: [8] = -1 3 -2 5 3 -5 2 2 Требуется найти максимальную сумму подпоследовательности, в данном примере: 3 - 2 + 5 + 3 = 9 Я решаю данную задачу следующим образом, сохраняю индексы с положительными числами. Нахожу массив с суммами, ищу максимум в интервалах с положительными индексами, однако получаю ответ: 11.

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

int main() {
    
    int n;
    scanf_s("%d", &n);

    vector <int> numbers(n);
    vector <int> sum(n);
    vector <int> positive;
    for (int i = 0; i < n; i++) {
        int temp; scanf_s("%d", &temp);
        if (temp > 0) {
            positive.push_back(i);
        }
        numbers[i] = temp;
        if (i == 0)
            sum[i] = numbers[i];
        else
            sum[i] = sum[i-1] + numbers[i];
    }

    for (int i = 0; i < n; i++)
        cout << sum[i] << " ";
}

Answer 1

const a = [-1, 3, -2, 5, 3, -5, 2, 2];

let maxSum, i, j, sum;
for (i = 0; i < a.length; i++) {
  sum = a[i];
  maxSum = maxSum > sum? maxSum : sum;
  for (j = i + 1; j < a.length; j++) {
    sum += a[j];
    maxSum = maxSum > sum? maxSum : sum;
  }
}

console.log('Max sum =', maxSum);

Answer 2

Вроде так?

int main()
{
    size_t n;
    cin >> n;
    vector<int> a;
    copy_n(istream_iterator<int>(cin),n,back_inserter(a));
    partial_sum(a.begin(),a.end(),a.begin(),
                [](int a, int b){ return a + b >= 0 ? a + b : 0; });
    cout << *max_element(a.begin(),a.end());
}

Вот еще одна "Кама Сутра" :)

struct Max
{
    int& operator*() { return cur; }
    void operator++(){ cur = mx = max(mx,mxe = max(0,mxe+cur)); }
private:
    int cur, mx = 0, mxe = 0;
};

int main()
{
    size_t n;
    cin >> n;
    cout << *copy_n(istream_iterator<int>(cin),n,Max{});

}

Answer 3

Я следовал классическому алгоритму, который описал Akina в своём комментарии. Хранить числа не требуется. Хранятся два максимума: max - текущий максимум вообще и max_ending_here - максимальная сумма при условии что подмассив кончается на текущем элементе.

Когда приходит очередное значение v, оно добавляется к max_ending_here. Если сумма осталась положительной, то это новая максимальная сумма отрезка последовательности чисел (тут пауза чтобы подумать почему это правда). Если сумма стала отрицательной, её заменяют нулем - суммой пустой последовательности.

#include <algorithm>
#include <iostream>

int main() {
    int n;
    std::cin >> n;

    int max = 0;
    int max_ending_here = 0;
    for (int i = 0; i < n; ++i) {
        int v;
        std::cin >> v;
        max_ending_here = std::max(0, max_ending_here + v);
        max = std::max(max, max_ending_here);
    }
    std::cout << max << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -O3 max-subrange-sum.cpp

$ echo 8 -1 3 -2 5 3 -5 2 2 | ./a.out 
9

БЛОГ НА HUSL

Наибольшая сумма подпоследовательности

Ответы (3 шт):