Найти начало и конец наибольшей непрерывной суммы подпоследовательности
Это моя программа для поиска самой большой непрерывной суммы подпоследовательностей. Я могу рассчитать сумму. Как этот код можно изменить, чтобы найти начальный и конечный индексы этой максимальной суммы подпоследовательности?
int maxSubArraySum(int a[], int size)
{
int final_max = 0, curr_max = 0;
for (int i = 0; i < size; i++)
{
curr_max = curr_max + a[i];
if (curr_max < 0)
curr_max = 0;
else if (final_max < curr_max)
final_max = curr_max;
}
return final_max;
}
Решение
Вам просто нужно запомнить индекс, где вы начинаете сумму и где сумма заканчивается.
struct SumAndRange{
int sum;
int start;
int stop;
SumAndRange() : sum(0),start(0),stop(0) {}
};
SumAndRange maxSubArraySum(int a[], int size) {
SumAndRange curr; // we will start with the sum of the first element
SumAndRange final;
for (int i = 0; i < size; i++) {
curr.sum = curr.sum + a[i];
if (curr.sum < 0) { // if we reset the sum it will
curr.sum = 0; // start with the next index
curr.start = i+1;
curr.stop = i+1; // ...and we also handle the case of
// the sum is only one element
} else { // otherwise the sum continues with
curr.stop = i; // this index
if (final.sum < curr.sum) { final = curr; }
}
}
return final;
}
int main() {
int a[] = { 2,-6,7,-3,12};
SumAndRange sar = maxSubArraySum(a,5);
std::cout << sar.sum << " " << sar.start << " " << sar.stop << std::endl;
return 0;
}
Другие решения
Других решений пока нет …