[C] Individuare la sequenza di k numeri in un array avente somma massima

[Molosso11]

Leggere o generare una sequenza di n numeri interi e un k <= n. Stampare l'array letto o generato. Individuare e stampare la sequenza di k numeri contigui avente somma massima.

Esempio. Se k = 3 e l’array è:

[3, 5, 8, 1, 9, 7]

La prima sequenza di tre elementi (3, 5, 8) ha somma 16,
la seconda sequenza (5, 8, 1) ha somma 14,
la terza (8, 1, 9) ha somma 18,
la quarta (1, 9, 7) ha somma 17,
per cui viene stampata la sequenza (8, 1, 9).

IMPORTANTE: Organizzare il programma in funzioni (una per leggere l’ array, una per stamparlo, una per individuare la sequenza massima). Non utilizzare array ausiliari, non introdurre variabili globali.

Queste sono le funzioni che ho creato per generare l'array

#include<stdio.h>
#include<stdlib.h>
#define MAX 100
void crearray(int A[MAX], int n);
void stamparray(int A[MAX], int n);

main()
{
      int i, n, A[MAX];
      printf("Quanti elementi vuoi inserire nell' array?");
      scanf("%d", &n);
      crearray(A, n);
      stamparray(A, n);
      system("PAUSE");
      return 0;
}

void crearray(int A[MAX], int n)
{
     int i;
     printf("Inserisci gli elementi dell'array: ");
     for(i=0; i<n; i++)
     scanf("%d", &A[i]);
     return;
}

void stamparray (int A[MAX], int n)
{
     int i;
     for(i=0; i<n; i++)
     printf("%d", A[i]);
     printf("\n\n");
     return;
}

Il mio problema è creare la funzione per individuare la somma massima tra le sequenze, non riuscendo a recuperare tutte le sequenze di k numeri dell'array.
Spero in un vostro gentile aiuto.
Grazie in anticipo

[oregon]

Originariamente inviato da Molosso11
... non riuscendo a recuperare tutte le sequenze di k numeri dell'array.

Devi chiedere il valore k all'utente (che sia <=n) e poi ti servi di un ciclo "esterno" per individuare l'inizio delle sequenze e un ciclo "interno" per identificare tutti i valori della singola sequenza.

[Molosso11]

Originariamente inviato da oregon
Devi chiedere il valore k all'utente (che sia <=n) e poi ti servi di un ciclo "esterno" per individuare l'inizio delle sequenze e un ciclo "interno" per identificare tutti i valori della singola sequenza.

si so che devo chiedere all'utente il valore di k ma, non riesco a recuperare e quindi poi a sommare tra di loro, tutte le sequenze di k numeri dell'array...

[oregon]

E ti ho detto come fare ...

[Molosso11]

sempre con la vostra gentilezza, potreste postarmi una vostra soluzione? Grazie.

[oregon]

E' anche possibile che tu tenti di sviluppare i due cicli di cui ti ho parlato e parliamo degli eventuali problemi ...

[Molosso11]

Diciamo che questa è l'intuizione che ho avuto io ma, sono sicuro di aver in gran parte sbagliato...

void seequenzamassima(int A[MAX], int n)
{
     int i, k, somma, sommamax;
     printf("Per quanti numeri vuoi effettuare le somme?");
     scanf("%d", &k);
     if(k>n){
             printf("Inserisci un valore minore del numero degli elementi dell'array");
             scanf("%d", &n);
             }
     else{
          for(i=0; i<n; i++){
            for(k=3; k<i; k++){
                     somma = somma + A[k];
                     }
            }
     if(somma > sommamax){
              somma = sommamax;
              }
     return;
}

[oregon]

Le variabili n e k non le devi utilizzare per i cicli perché il loro valore non deve cambiare.

Userai altre due variabili, i e j, per i due cicli di cui ti parlavo.

Nell'esempio che hai mostrato all'inizio, avrai

n = 6
k = 3

[3, 5, 8, 1, 9, 7]

e quindi le sequenze saranno

3 5 8
5 8 1
8 1 9
1 9 7

Il primo ciclo (con indice i) ti servirà ad identificare il primo elemento delle sequenze (quelli sottolineati), quindi quelli con l'indice 0, 1, 2 e 3. Il ciclo esterno sarà quindi

for(i=0; i<n-k+1; i++)

Il secondo ciclo (con indice j) ti servirà ad esaminare tutti i k elementi richiesti. Sarà

for(j=0; j<k; j++)

L'elemento da considerare nel ciclo più interno sarà

A[i+j]

Inoltre tieni presente che, prima che inizi a calcolare una somma, la variabile

somma

va azzerata

[Molosso11]

Originariamente inviato da oregon
Le variabili n e k non le devi utilizzare per i cicli perché il loro valore non deve cambiare.

Userai altre due variabili, i e j, per i due cicli di cui ti parlavo.

Nell'esempio che hai mostrato all'inizio, avrai

n = 6
k = 3

[3, 5, 8, 1, 9, 7]

e quindi le sequenze saranno

3 5 8
5 8 1
8 1 9
1 9 7

Il primo ciclo (con indice i) ti servirà ad identificare il primo elemento delle sequenze (quelli sottolineati), quindi quelli con l'indice 0, 1, 2 e 3. Il ciclo esterno sarà quindi

for(i=0; i<n-k+1; i++)

Il secondo ciclo (con indice j) ti servirà ad esaminare tutti i k elementi richiesti. Sarà

for(j=0; j<k; j++)

L'elemento da considerare nel ciclo più interno sarà

A[i+j]

Inoltre tieni presente che, prima che inizi a calcolare una somma, la variabile

somma

va azzerata

Innanzitutto grazie mille per la disponibilità e per l'aiuto che mi stai dando.

Da quel che ho capito quindi la funzione diventerebbe così:

void sequenzamassima(int A[MAX], int n)
{
     int i, j, k, somma = 0, sommamax;
     printf("Per quanti numeri vuoi effettuare le somme?");
     scanf("%d", &k);
     if(k>n){
             printf("Inserisci un valore minore del numero degli elementi dell'array: ");
             scanf("%d", &n);
             }
     else{
          for(i=0; i<n-k+1; i++){
            for(j=0; j<k; j++){
                     somma = somma + A[i+j];
                     }
                 }
          }
     if(somma > sommamax){
              somma = sommamax;
              }
     return;
}

[oregon]

Quasi ... non azzeri somma ogni volta che inizi una nuova somma ...