Trouver une sous-séquence du tableau à chaque intervalle n

Question

Je voudrais trouver la séquence dans une liste de nombres où elle renvoie la somme maximale. Les restrictions sont qu'elle doit être à chaque n intervalle. Par exemple :

n \= 4 ;
A \= [1 4 3 2 9 8 7 6]

La sous-séquence optimale est donc 4 + 8 = 12 aux positions 1 et 5 (nous supposons que la numérotation des positions commence à 0).

Mon idée : Je sais que c'est un problème de programmation dynamique. Cependant, je ne sais pas comment l'envisager sous la forme d'un problème plus petit. J'espère que cela a un sens. Je vous remercie !

Answer 1

Si tous les nombres sont non négatifs, il est préférable de faire la sous-séquence la plus longue possible pour obtenir la somme maximale. La restriction de l'intervalle signifie qu'il y a seulement n possibilités de choisir l'indice de départ. Dans l'exemple, vous avez ces quatre possibilités :

1 9
4 8
3 7
2 6

Calculez la somme de chacun d'eux et choisissez le plus grand.

Answer 2

Vous pouvez vous tourner vers le reste de l'indice des éléments par n pour diviser les éléments en sous-ensemble d'élément distant n l'un de l'autre. En additionnant ensuite tous les éléments de chaque sous-ensemble, on peut trouver celui dont la somme est la plus élevée.
La séquence (indice dans le tableau original, valeur) à ce stade peut être facilement trouvée.
Je veux dire quelque chose comme ceci (faites attention à l'indentation)

   n=lenght of the inteval;
   group[n]=[]
   sum[n]=[0,....,0];
   for i=0,...,array.lenght-1
      k=i%n;
      insert the i-th element of the array in group[k];
   for j=0,...,n-1
      sum[j]=sum of all element in group[j];
   max=0;
   for k=0,...,n-2
      if(sum[k]<sum[k+1])
        max=k+1;
   for u=0,...,group[max].lenght
      index=u*max;
      print (index, group[max][u])        

Je ne suis pas sûr que ce soit l'approche que vous recherchez, mais cela peut peut-être vous aider.