Die maximale Summe in einem Zahlenfeld finden

Ich muss ein Programm schreiben, das sequenzielle Elemente eines Arrays summiert und die maximale Summe ausgibt. Wie Sie sehen werden, funktioniert mein Algorithmus nicht, wenn alle Elemente negativ sind.Die maximale Summe in einem Zahlenfeld finden

#include <iostream> 

int main() 
{ 
    int nums[1000] = {-1,-3,-4,-2,-5,-1,-9,-4,-2,-2}; 
    int sums[100][100]; 
    int n = 9; 

    for(int i = 0; i <= n; i++) { 
     for(int j = n; j >= i; j--) { 
      for(int k = j; k >= i; k--) { 
       sums[i][j] += nums[k]; 
      } 
     } 

    } 

    int max_sum = 0; 
    int max_begin; 
    int max_end; 

    for(int i = 0; i <= n; i++) { 
     for(int j = i+1; j <= n; j++){ 
       std::cout << "i = " << i << " j = " << j << ": " << sums[i][j] << "\n"; 
      if(max_sum < sums[i][j]) { 
       max_sum = sums[i][j]; 
       max_begin = i; 
       max_end = j; 
       } 
      } 
     } 

    std::cout << "Maximum: " << max_sum << " bei i = " << max_begin << " bis j = " << max_end; 

    return 0; 
}

Ich habe bereits versucht, diese Lösung

#include <climits> 
... 
int max_sum = INT_MIN; 
...

Während dies völlig in Ordnung funktioniert wir nicht climits in unserem Vortrag hatte noch so für eine andere Art und Weise ich suche.

Quelle

2017-11-27 Brain Damage

reaktivieren Warum können Sie 'climits' nicht verwenden? Was ist mit ['std :: numeric_limits'] (http://en.cppreference.com/w/cpp/types/numeric_limits)? Sie vermeiden bewusst die kanonische Lösung, aber wofür? –

Ich kann 'Climits' verwenden. Aber ich dachte, dass es eine alternative Lösung geben muss, da wir in unserem Vortrag noch keinen Höhepunkt hatten und ich daran interessiert bin, es zu wissen. –

Wie soll ich 'std :: numeric_limits' verwenden? Ich kann nicht sehen, wie man es in meinen Code einbindet –

Wechseln zu:

int max_sum = sums[0][0];

diese Weise werden Sie nie über den Bereich von Zahlen zu kümmern.

Quelle

2017-11-27 12:12:56

Aber wird sich auf einen nicht leeren Bereich verlassen. –

@PasserBy es ist hart codiert 1000x1000 zu sein –

Ich neige nicht, Übungsprobleme zu wörtlich zu nehmen. Sollten Sie nicht mit Best Practices antworten? –

Dies ist eine der Hauptmotivationen für einen Typ std::optional (wenn alle Werte in einem Bereich gültig sind). Wenn Sie es nicht verwenden können, können wir es für unsere Zwecke mit einem einfachen boolean imitieren:

bool max_set = false; 
int max_sum = 0; 

// ... 
if (!max_set || max_sum < sums[i][j]){ 
    max_set = true; 
    max_sum = sums[i][j]; 
}

Wir können eine einfache Klasse machen es weiter zu imitieren, wenn wir (ungetestet Code) möchten:

class optional_int{ 
    bool is_set = false; 
    int value = 0; 
public: 
    bool operator()() const{return is_set;} 
    int& operator=(int _value){value = _value; is_set=true; return value;} 
    int& get(){ 
     if (!is_set){throw std::logic_error("attempting to access unset optional");} 
     return value; 
}; 

optional_int max_sum; 
//... 
if (!max_sum || max_sum.get() < sums[i][j]){ 
    max_sum = sums[i][j]; 
}

Wir können weiterhin diesen Typ immer generischer machen, aber wir würden nur std::optional

Quelle

2017-11-27 12:40:15 AndyG

Die maximale Summe in einem Zahlenfeld finden

Antwort

Verwandte Themen