Нахождение смежного подмассива с максимальной суммой

Question

Нахождение смежного подмассива с максимальной суммой

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

#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;
}

но я также хочу найти начальную и конечную позиции этого смежного подмассива с максимальной суммой. Я попытался добавить пару строк в вышеупомянутой программе, но это не сработало. поэтому мой вопрос, как я могу получить начальную и конечную позиции этого подмассива с максимальной суммой? Благодарю.

3

arrays c++kadanes-algorithm

Решение

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

Расширьте сигнатуру функции следующим образом:

int kadane(int a[], int n, int *start, int *end)

В конце функции перед возвратом установите два параметра следующим образом:

    *start = _start;
*end = _end;
return max_till_now;
}

И назовите это так:

int start, end;
int m = kadane(a, 6, &start, &end);
printf("sum: %i, start %i, end: %i\n",m, *start, *end);

2

Чтобы передать больше из функции, используйте указатели. Ниже должно работать.

#include <cstdio>

using namespace std;

int kadane(int a[], int n, int* start, int* end ) {

int max_ending_here = a[0], max_till_now = a[0];

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;
}
}

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 start = 0, end = 0;
int m = kadane(a, 6, &start, &end);
printf("Max: %d, Start: %d, End: %d\n",m, start, end);
return 0;
}

1

Источник

Accepted Answer

Попробуйте использовать этот код в качестве основы, чтобы делать то, что вы хотите. Просто игнорируйте некоторые слова на португальском (мой родной язык).

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

void seg_max(int *v, int n, int & x, int &y , int & max){
int i,j;
int soma;
max = -1;
for(i=0;i<n;i++){
soma = 0;
for(j=i;j<n;j++){
soma += v[j];
if( soma > max ){
max = soma;
x = i;
y = j;
}
}
}
}

int main(){
int x,y,max;
int v[] = {-2,1,-3,4,-1,2,1,-5,4};
seg_max(v,9,x,y,max);
printf("max sum [%d-%d] with the sum equal to %d\n", x,y,max);
}

1