Calculer les bénéfices plus rapidement que O (n!)

Question

Donc, la semaine dernière, j'ai posté un problème pour l'ACM ICPC Sud-Est Régionaux ici ->Algorithm to calculate the number of 1s for a range of numbers in binary. Il a été plutôt bien reçu et n'a toujours pas été résolu, alors j'ai pensé pourquoi ne pas poser une autre question que mon équipe ne pouvait pas résoudre.

Le problème.

Vos amis viennent d'ouvrir une nouvelle entreprise, et vous voulez voir comment ils se débrouillent. L'entreprise fonctionne depuis plusieurs jours et vos amis ont enregistré leurs bénéfices nets chaque jour. Vous voulez connaître le bénéfice total le plus élevé réalisé par vos amis pendant une période consécutive d'au moins un jour. Par exemple, si vos amis profits ressemblaient à ceci:

Day 1: -3 
Day 2: 4 
Day 3: 9 
Day 4: -2 
Day 5: -5 
Day 6: 8 

Leur profit maximum sur toute la durée serait de 14, du jour 2 à 6.

Entrée
Il y aura plusieurs cas de test dans l'entrée. Chaque test élémentaire commence par un entier N (1 < = N < = 250 000) sur sa propre ligne, indiquant le nombre de jours. Sur chacune des N lignes suivantes, il y aura un seul entier P (-100 < = P < = 100), indiquant le bénéfice pour ce jour. Les jours sont spécifiés dans l'ordre. L'entrée se termine par une ligne avec un seul 0

sortie
Pour chaque test, la production d'un seul nombre entier, représentant le maximum de profit sur toute la durée non vide de temps. Imprimer chaque entier sur sa propre ligne sans espaces. N'imprimez aucune ligne de planche entre les réponses.

Exemple d'entrée

6 
-3 
4 
9 
-2 
-5 
8 
2 
-100 
-19 
0 

Exemple de sortie

14 
-19 

---

Le code pour résoudre ce problème est assez simple si vous ne vous inquiétez pas sur l'efficacité mais la seule comme il a été résolu au concours était à O (n!), w qui est inacceptable. J'espère que le débordement de pile peut faire mieux

Bonne chance!

EDIT

---

Juste pour garder cette mise à jour est ici code complet qui permet de résoudre ce problème dans O (n).

import java.util.Scanner; 

public class Profits { 
    public static int seqStart=0, seqEnd=-1; 
    public static void main(String args[]) { 
     Scanner s = new Scanner(System.in); 
     while (s.hasNextLine()) { 
      int current = s.nextInt(); 
      if (current == 0) 
       break; 
      else { 
       int count = current; 
       int[] a = new int[count]; 
       for (int x = 0; x < count; x++) { 
        a[x] = s.nextInt(); 
       } 
       System.out.println(max_subarray(a)); 
      } 
     } 
    }  
    private static int max_subarray(int[] a) { 
     int maxSum = a[0], thisSum = a[0]; 
     for(int i=0, j=0;j<a.length;j++) { 
      thisSum = thisSum + a[j]; 
      if(thisSum > maxSum) { 
       maxSum = thisSum; 
       seqStart = i; 
       seqEnd = j; 
      } 
      else if (thisSum < 0) { 
       i = j+1; 
       thisSum = 0; 
      } 
     } 
     return maxSum; 
    }  
} 

Answer 1

Vous recherchez le Maximum Subarray Problem.
Il peut être résolu en O (n), comme décrit par Wikipedia.