Алгоритм Кадана — Найти начальный и конечный индексы непрерывного подмассива наименьшей суммы в переполнении стека

Question

Алгоритм Кадана — Найти начальный и конечный индексы непрерывного подмассива наименьшей суммы в переполнении стека

Я пытаюсь найти начальный и конечный индекс непрерывного подмассива наименьшей суммы. Я пытался много раз, но я не мог найти.

Кто-нибудь может мне помочь с этим в C ++?

Код для нахождения наименьшей суммы смежных подмассивов:

#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {3, -4, 2, -3, -1, 7, -5};
int n = sizeof(arr) / sizeof(arr[0]);
int min_ending_here = INT_MAX;
int min_so_far = INT_MAX;
for (int i=0; i<n; i++)
{
if (min_ending_here > 0)
min_ending_here = arr[i];

else
min_ending_here += arr[i];

min_so_far = min(min_so_far, min_ending_here);
}
cout<<"minimum sum = "<<min_so_far;
}

Выход: minimum sum = -6

0

c++kadanes-algorithm

Решение

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

Я протестировал его с 2 массивами (текущий (результат [1,4]) и прокомментировал (результат [3,3]), см. Код):

#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {3, -4, 2, -3, -1, 7, -5};
//int arr[] = {2, 6, 8, 1, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int min_ending_here = INT_MAX;
int min_so_far = INT_MAX;

int infimum = INT_MAX; // hold minimum value.
std::pair<int, int> idx(-1, -1); // subarray's indexes

for (int i=0; i<n; i++)
{
if (min_ending_here > 0)
{
min_ending_here = arr[i];
}
else
min_ending_here += arr[i];

min_so_far = min(min_so_far, min_ending_here);

// indexes addition
if( min_so_far == min_ending_here)
{
infimum = min(arr[i], infimum);
if( infimum == arr[i] )
{
idx.first = i;
}
idx.second = i;
}
// << indexes addition

}
cout<<"minimum sum = "<<min_so_far << " indexes: " << idx.first << " " << idx.second;
}

1

Источник

Accepted Answer

Предполагая, что если существует несколько смежных подмассивов с минимальной суммой, мы возьмем тот с минимальным начальным индексом, мы можем изменить вышеуказанное решение, как показано ниже:

#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = {3, -4, 2, -3, -1, 7, -5};
int n = sizeof(arr) / sizeof(arr[0]);
int min_ending_here = INT_MAX;
int min_so_far = INT_MAX;
int last_idx = 0; // indication of fresh start of contiguous summation
int start_idx; // for holding start index
int end_idx; // for holding end index
for (int i=0; i<n; i++) {
if (min_ending_here > 0) {
min_ending_here = arr[i];
last_idx = i;
}
else {
min_ending_here += arr[i];
}
if (min_so_far > min_ending_here) {
min_so_far = min_ending_here;
start_idx = last_idx;
end_idx = i;
}
}
cout<<"minimum sum = "<<min_so_far<<endl;
cout<<"start index = "<<start_idx<<endl;
cout<<"end index = "<<end_idx<<endl;
}

2