Как мне изменить алгоритм Кадане, чтобы найти элементы подмассива, которые вносят вклад в максимальную сумму?

Что я сделал до сих пор:

Я узнал сумму, используя алгоритм Кадане.

Я создал вектор «res», который хранит элементы при выполнении условий.

Проблема:
Например, когда входные данные являются массивом: {-2, -3, 4, -1, -2, 1, 5, -3}
Результирующий массив содержит правильные элементы подмассива и 1 дополнительный элемент, который добавляется при сбое условия.

tldr: Код возвращает выходной подмассив в виде: {4 -1 -2 1 5 -3}
тогда как правильный вывод должен быть {4, -1, -2, 1, 5}

#include <bits/stdc++.h>
using namespace std;

int main()
{
int i, a[10], n, temp_sum=0, final_sum=0;
vector<int> res;
cin >> n;                               //getting array size input
for(i=0; i<n; i++)
{
cin >> a[i];                        //getting array elements input
}
temp_sum=a[0];                          //initializing to first element
final_sum=a[0];
for(i=1; i<n; i++)
{
if(a[i]>temp_sum+a[i])       //if element is greater than sum so far
{
temp_sum = a[i];
res.clear();
res.push_back(a[i]);
}
else
{
temp_sum = a[i] + temp_sum;
cout << temp_sum << " " << final_sum << " " << a[i] << "\n";
res.push_back(a[i]);
}
if(temp_sum>final_sum)
{
final_sum = temp_sum;
}
}
cout << final_sum << "\n";                  //displaying maximum sum
for(i=0; i<res.size(); i++)                 //displaying result vector
{
cout << res[i] << " ";
}
return 0;
}

-2

Решение

Обратите внимание, что вы выполняете

res.push_back(a[i]);

в любом случае и не обновлять Res, если if(temp_sum>final_sum) не удалось

Кстати, состояние if(a[i]>temp_sum+a[i]) равно temp_sum <0 (не влияет на результат)

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]