Scrive un programma che, per matrice dati di valori interi (contenente numeri interi negativi) trova la somma massima di elementi successivi nell'array.Trova la somma massima di elementi nell'array
Esempio:
2, 3, -6, -1, 2, -1, 6, 4, -8, 8
esprime
Sto cercando una soluzione che è faste r di O (N^2).
Questo è in realtà un problema da manuale Ho studiato in un college (algoritmi e strutture dati in C da Mark Allen Weiss) ... Si tratta di un bellissimo ed elegante soluzione e risolve a O (N)
int MaxSubsequenceSum(int A[])
{
int sum = 0, maxSum = 0;
for (int j = 0; j < A.Length; j++)
{
sum = sum + A[j];
if (sum > maxSum)
maxSum = sum ;
else if (sum < 0)
sum = 0;
}
return maxSum;
}
Il tuo post è stato modificato da un utente anonimo e quindi approvato. Potresti confermare che questi cambiamenti sono, in effetti, positivi? Sembrava cambiare la logica in modo significativo. – Gray
no non l'ho approvato e non migliora significativamente la risposta. Penso che sia stato fatto per i punti –
È stato fatto da un utente anonimo, quindi nessun rappresentante è stato assegnato. Sentiti libero di tornare indietro. Hanno [lasciato un commento] (http://stackoverflow.com/posts/12339772/revisions) sul perché lo hanno fatto. – Gray
è possibile innanzitutto ordinare l'array data in ordine decrescente e poi riassumere i primi tre elementi della matrice da: sum=arr[0]+arr[1]+arr[2] dal INIZIALIZZA somma sum=0 e stampare.
1,2,5,6 non sono successivi. Se non si dispone di restrizioni sul sottoinsieme che può essere preso, questo è il problema Sotto-somma, che è NP-Completo, ma non penso che sia il caso. – amit
Ci scusiamo per l'equivoco. Ho fatto un errore nella descrizione e nell'esempio. :) Ho aggiornato entrambi. – user1106337
Una scansione lineare può risolvere questo problema. Basta sommare e confrontare con il massimo corrente, se la somma è <0, quindi resettare la somma a 0 e continuare. Questa soluzione golosa ha dimostrato di essere corretta. Si chiama algoritmo di Kadane: http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh