Massimo sottoarray in tempo lineare

[Giova411]

Senza usare però il Divide Et Impera vorrei scrivere un algoritmo (non ricorsivo quindi) per risolvere il problema del massimo sottoarray interno ad un array. Ossia trovare il sottoarray non vuoto di $A$ i cui valori hanno la somma massima e siano elementi contigui in $A$. Ovviamente ci possono essere elementi sia positivi che negativi.
---
La strada per la soluzione potrebbe trovarsi iniziando da sinistra per procedere verso destra, memorizzando il massimo sottoarray trovato fino a quel punto. Conoscendo un massimo sottoarray di $A[1..j]$, si aggiorna la soluzione considerando il massimo sottoarray che termina con l'indice $j+1$ sulla base della seguente osservazione: un massimo sottoarray di $A[1..j+1]$ è un massimo sottoarray di $A[1..j]$ o un sottoarray $A[i..j+1]$, per $1<=i<=j+1$.
Determinare un massimo sottoarray della forma $A[i..j+1]$ in tempo costante, supponendo di conoscere un massimo sottoarray che termina con l'indice $j$.

[apatriarca]

Hai un massimo sottoarray che termina all'indice \(j\). Un massimo sottoarray che termina in \(j+1\) non può ovviamente partire da un indice \(k < i\) o \(i < k \leq j\). Avresti altrimenti che \(A[k..j]\) è un sottoarray con la somma maggiore di \(A[i..j]\). Se la somma di questo sottoarray è quindi positiva, si deve necessariamente avere che \(A[i..j+1]\) è l'array che stai cercando. D'altra parte potresti avere che la somma di questo sottoarray di somma massimo ha una somma negativa, per cui \(A[j+1] > A[i..j+1]\). Il caso in cui il sottoarray ha somma nulla puoi considerarlo come preferisci..

[Giova411]

Miglioramenti e consigli?
C++

#include <iostream>
using namespace std;
void sommamassima(int a[], int n){
int inizio=0;
int inizioprov=0;
int fine=0;
int sommaprov=0;
int sommamassima=0;
for (int i=0; i<n; i++){
  sommaprov = sommaprov + a[i];
  if(sommaprov<0) {
   sommaprov = 0;
   inizioprov = i+1;
  }else if (sommaprov>sommamassima){
   sommamassima = sommaprov;
   inizio = inizioprov;
   fine = i;
   }
 }
cout<<"Indice d'inizio sottoarray: "<<inizio<<", indice finale: "<<fine<<", somma massima: "<<sommamassima <<endl;
}
int main() {;
int a[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
int dim = sizeof(a)/sizeof(int);
for(int i=0; i<dim; i++){
 cout<<a[i]<<" ";
 }
cout<< "\n";
sommamassima(a, dim);
return 0;
 }

Grazie apatriarca!

[vict85]

Penso che vada abbastanza bene. Puoi vedere la pagina di wiki corrispondente per qualche piccolo miglioramento.

[Giova411]

Cosa farei senza di voi!?!!
Grazie!