вот моя программа, чтобы найти максимальную сумму подмассива (смежного) из данного массива. использовать алгоритм Кадане очень просто.
#include <iostream>
#include <cstdio>
using namespace std;
int kadane(int a[], int n) {
int max_ending_here = a[0], max_till_now = a[0];
int _start = 0, _end;
bool s=true;
for (int i = 1; i < n; ++i)
{
max_ending_here = max(a[i], max_ending_here + a[i]);
if(max_ending_here + a[i] > a[i] && s==false) _start = i, s=true;
max_till_now = max(max_ending_here, max_till_now);
if(max_ending_here + a[i] < a[i] && s==true) _end=i-1,s=false;
}
printf("S = %d , E = %d\n",_start,_end);
return max_till_now;
}
int main(int argc, char const *argv[])
{
//int a[10] = {1,-3,2,-5,7,6,-1,-4,11,-23};
int a[6] = {-8,-1,-1,-1,-1,-5};
int m = kadane(a, 6);
printf("%d\n",m);
return 0;
}
но я также хочу найти начальную и конечную позицию этого непрерывного подмассива, который имеет максимальную сумму. Я попытался добавить пару строк в приведенную выше программу, но это не сработало. Итак, мой вопрос в том, как я могу получить начальную и конечную позиции этого подмассива с максимальной суммой? Благодарю.