3

これは、特定の配列からサブ配列（連続）の最大合計を見つけるための私のプログラムです。kadane のアルゴリズムを使用すると非常に簡単です。

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

しかし、最大合計を持つ連続したサブ配列の開始位置と終了位置も見つけたいです。それを行うために上記のプログラムに数行追加しようとしましたが、うまくいきませんでした。私の質問は、最大合計を持つそのサブ配列の開始位置と終了位置を取得するにはどうすればよいですか? ありがとう。

4

3 に答える 3

2

関数シグネチャを次のように拡張します。

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

関数の最後で、return の前に次のように 2 つのパラメーターを設定します。

    *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);
于 2015-05-15T18:38:03.100 に答える
1

関数からさらに多くを渡すには、ポインターを使用します。以下で動作するはずです。

#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;
}
于 2015-05-15T18:47:59.043 に答える
1

このコードをベースとして使用して、やりたいことを実行してみてください。ポルトガル語 (私の母国語) のいくつかの単語は無視してください。

#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);
}
于 2015-05-15T18:45:09.693 に答える