Maximale Summe in einem Subarray

Question

Sie erhalten ein Array von N Integer-Zahlen.
Die maximale Summe des Arrays ist die maximale Summe der Elemente eines nicht leeren aufeinander folgenden Subarrays dieses Arrays.
Zum Beispiel ist die maximale Summe des Arrays [1, -2, 3, -2, 5] 6, weil die Summe des Subarrays [3, -2, 5] 6 ist und es unmöglich ist, ein größeres Subarray zu erreichen Summe.
Jetzt dürfen Sie nicht mehr als ein Element aus dem angegebenen Array entfernen. Was ist die maximal mögliche maximale Summe der resultierenden Anordnung, die Sie dadurch erreichen können?

Ich teste meinen Code mit meinen eigenen Testfällen. Ich bekomme korrekte Ausgabe auf dev-C++. Aber wenn ich meinen Code online teste, bekomme ich falsche Antwort. Ich bin nicht in der Lage herauszufinden, was das Problem ist.

#include <stdio.h> 
#include <limits.h> 
#include <stdlib.h> 
struct result{ 
    long long int start; 
    long long int end; 
    long long int sum; 
}res; 
long long int find_max(long long int a[],long long int n) 
{ 
    long long int max=LLONG_MIN; 
    long long int i; 
    for(i=0;i<n;++i) 
    { 
     if(a[i]>max) 
      max=a[i]; 
    } 
    return max; 
} 
long long int max_sub(long long int a[],long long int n) 
{ 
    long long int i; 
    long long int min,sum1=0; 
    struct result max,max_curr,*maxsub; 
    maxsub=calloc(sizeof(res),n); 
    max.sum=LLONG_MIN; 
    max_curr=max; 
    for(i=0;i<n;++i) 
    { 
     if(max_curr.sum<0) 
     { 
      max_curr.sum=a[i]; 
      max_curr.start=i; 
      max_curr.end=i; 
     } 
     else 
     { 
      max_curr.sum+=a[i]; 
      max_curr.end=i; 
     } 
     if(max_curr.sum>max.sum) 
     { 
      max=max_curr; 
     } 
     maxsub[i]=max; 
    } 
    min=0; 
    for(i=maxsub[n-1].start;i<=maxsub[n-1].end;++i) 
    { 
     if(a[i]<0) 
     { 
      if(min==0 || a[i]<min) 
       min=a[i]; 
     } 
    } 
    sum1=maxsub[n-1].sum-min; 
    return sum1; 
} 
int main() 
{ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
     long long int n,i; 
     scanf("%lld",&n); 
     long long int a[n]; 
     for(i=0;i<n;++i) 
      scanf("%lld",&a[i]); 
     long long int sum=0; 
     sum=find_max(a,n); 
     if(sum<=0) 
     { 
      printf("%lld\n",sum); 
     } 
     else 
     { 
      sum=max_sub(a,n); 
      printf("%lld\n",sum); 
     } 

    } 
    return 0; 
} 

Answer 1

Warum Sie subtrahieren geringste Anzahl von Ergebnis:

/*min=0; 
for(i=maxsub[n-1].start;i<=maxsub[n-1].end;++i) 
{ 
    if(a[i]<0) 
    { 
     if(min==0 || a[i]<min) 
      min=a[i]; 
    } 
}*/ 
sum1=maxsub[n-1].sum;//-min; 
return sum1; // Works fine 

Answer 2

dieses Array try {1, -100, 6, -50, 5}. Sie entfernen minimum Element in Subarray mit maximaler Summe, aber je nach Ihrem Problem können Sie am besten ein Element aus ursprünglichen Array entfernen, um die Summe seiner zusammenhängenden Array zu maximieren, und das ist, warum Sie eine falsche Antwort erhalten.

Answer 3

Offensichtlich haben Sie den Kadane-Algorithmus implementiert, um das Max-Sum-Subarray in einem Array zu finden. Bei Array ist: [1, -2, 3, -2, 5]
Kadane des Ergebnis: [3, -2, 5]

Nun, was Sie tun, sind: das kleinste Element in dem Sub-Array entfernt , was leider falsch ist.
Angenommen Array ist: [1, -2, 3, -2, 5, -33, 5]
Kadanes Ergebnis: [3, -2, 5]
Ihre Ausgabe: [3, 5] , dh 8

Aber hier ist die richtige Antwort wäre die Auswahl Sub-Array [3, -2, 5, -33, 5] und die Beseitigung der '-33' und was dazu führt, um die Ausgabe zu sein: 11 (3+ 5 + 5-2)

Danke.
PS: Meine erste Antwort auf Stackoverflow. Dies ist nur eine Ausnahme, über die ich gesprochen habe, es gibt noch viel mehr.
Viel Glück!

Answer 4

#include<stdio.h> 
#include<limits.h> 
long long int sum; 
long long int rightsum(long long int a[], long int n, long int start, long int end) { 

    long int i; 
    long long int max_so_far=INT_MIN,max_ending_here=0; 
    for(i=start;i<=end;i++) 
    { 
     max_ending_here = max_ending_here + a[i]; 
     if (max_so_far < max_ending_here) 
     { 
      max_so_far = max_ending_here; 
     } 
    } 
    return max_so_far; 
} 
long long int leftsum(long long int a[], long long int n, long long int start, long long int end) { 

    long int i; 
    long long int max_so_far=INT_MIN,max_ending_here=0; 
    for(i=end;i>=start;i--) 
    { 
     max_ending_here = max_ending_here + a[i]; 
     if (max_so_far < max_ending_here) 
     { 
      max_so_far = max_ending_here; 
     } 
    } 
    return max_so_far; 
} 
long long int maxSum(long long int a[],long int n) { 

    long long int sum = rightsum(a, n, 1, n - 1); 
    long int i; 

    for (i = 0; i < n; i ++) { 

     long long int l = leftsum(a, n, 0, i - 1); 
     long long int r = rightsum(a, n, i + 1, n - 1); 


     if (((i > 0) && (i < n - 1)) && (l>=0) && (r>0) && (l+r>sum)) { 

      sum = l+r; 
      if(sum<sum+a[i]) 
      { 
       sum=sum+a[i]; 
      } 

     } 


     else if ((i > 0) && (l >= r) && (l>sum)) { 
      sum = l; 

      if(sum<sum+a[i]) 
      { 
       sum=sum+a[i]; 
      } 

     } 

     else if ((i < n - 1)) { 
      sum = r; 

      if(sum<sum+a[i]) 
      { 
       sum=sum+a[i]; 
      } 

     } 
    } 
    return sum; 
} 
int main() 
{ 
    int t; 
    long long i,n; 
    long long int a[100000]; 
    scanf("%d",&t); 
    while(t!=0) 
    { 
     scanf("%ld",&n); 
     for(i=0;i<n;i++) 
     { 
      scanf("%lld",&a[i]); 
     } 
     printf("%lld\n",maxSum(a,n)); 
     t--; 
    } 
    return 0; 
} 

Answer 5

Bitte diesen Thread schließen. OP versucht gerade in einem Online-Wettbewerb zu schummeln, indem er hier die Fragen stellt.

Answer 6

Nun, das ist nicht fair, die Leute haben hart gearbeitet, um es zu knacken. Dies ist Teil der laufenden Online-Wettbewerb auf Code-Chef, Bitte diesen Thread schließen.

EDIT: Der Wettbewerb ist nun vorbei, Bitte zur Diskussion :)