Wie kann ich die minimale Untersequenz mit LINQ auswählen?

Question

Wenn ich eine Reihe von Golf Ergebnisse haben:

-3, +5, -3, 0, +1, +8, 0, +6, +2, -8, +5 

Ich brauche eine Sequenz von drei benachbarten Zahlen zu finden, die die Mindestsumme haben. In diesem Beispiel wären die Teilsequenzen:

[-3, +5, -3] 
[+5, -3, 0] 
[-3, 0, +1] 
... etc ... 
[+2, -8, +5] 

und die minimale Sequenz [-3, 0, +1] mit einer Summe von -2 wäre.

Answer 1

Sie könnten diese LINQ-Abfrage verwenden:

int[] golfResult = { -3, +5, -3, 0, +1, +8, 0, +6, +2, -8, +5 }; 
var combinations = from i in Enumerable.Range(0, golfResult.Length - 2) 
        select new { 
         i1 = golfResult[i], 
         i2 = golfResult[i + 1], 
         i3 = golfResult[i + 2], 
        }; 
var min = combinations.OrderBy(x => x.i1 + x.i2 + x.i3).First(); 
int[] minGolfResult = { min.i1, min.i2, min.i3 }; // -3, 0, +1 

Natürlich müssen Sie es überprüfen, ob mindestens drei Ergebnisse in der Anordnung sind.

Answer 2

Wenn Sie es wirklich in LINQ tun möchten, können Sie diesen Weg gehen:

int length = 3; 
var scores = new List<int>() { -3, +5, -3, 0, +1, +8, 0, +6, +2, -8, +5 }; 
var results = 
    scores 
    .Select((value, index) => new 
    { 
     Value = scores.Skip(index - length + 1).Take(length).Sum(), 
     Index = index - length + 1 
    }) 
    .Skip(length - 1) 
    .OrderBy(x => x.Value) 
    .First() 
    .Index; 

Dies schafft eine zweite Liste, die alle Elemente Länge vorhergehenden summiert und sortiert sie dann. Sie haben

Answer 3

Ich bin mir nicht sicher, warum Sie dies mit LINQ tun würden. Ich denke, dass eine geradlinige iterative Lösung einfacher zu verstehen ist:

int[] scores = new[] { -3, 5, -3, 0, 1, 8, 0, 6, 2, -8, 5 }; 

int minimumSubsequence = int.MaxValue; 
int minimumSubsequenceIndex = -1; 

for (int i = 0; i < scores.Length - 2; i++) 
{ 
    int sum = scores[i] + scores[i + 1] + scores[i + 2]; 

    if (sum < minimumSubsequence) 
    { 
     minimumSubsequence = sum; 
     minimumSubsequenceIndex = i; 
    } 
} 

// minimumSubsequenceIndex is index of the first item in the minimum subsequence 
// minimumSubsequence is the minimum subsequence's sum.