let randGen = System.Random()
fun _ -> randGen.Next 300
let [<Literal>] ListSize = 100000
let k = 3
let list
= Array.
init ListSize
rand printfn "%A" list
let cache = System.Collections.Generic.Dictionary (list.Length + 2*k + 1)
seq {list.Length .. list.Length + 2*k} |> Seq.iter (fun i -> cache.Add(i, (0, [])))
for i in list.Length - 1 .. -1 .. 0 do
let maxSum, maxList =
seq {i + k .. i + 2*k}
|> Seq.map (fun i -> cache.[i])
|> Seq.maxBy fst
cache.Add(i, (list.[i] + maxSum, i :: maxList))
let maxSum, maxList = seq {0 .. k} |> Seq.map (fun i -> cache.[i]) |> Seq.maxBy fst
printfn "%i: %A" maxSum maxList
bGV0IHJhbmQgPQogICAgbGV0IHJhbmRHZW4gPSBTeXN0ZW0uUmFuZG9tKCkKICAgIGZ1biBfIC0+IHJhbmRHZW4uTmV4dCAzMDAKCmxldCBbPExpdGVyYWw+XSBMaXN0U2l6ZSA9IDEwMDAwMAoKbGV0IGsgPSAzCmxldCBsaXN0ID0gQXJyYXkuaW5pdCBMaXN0U2l6ZSByYW5kIApwcmludGZuICIlQSIgbGlzdAoKbGV0IGNhY2hlID0gU3lzdGVtLkNvbGxlY3Rpb25zLkdlbmVyaWMuRGljdGlvbmFyeSAobGlzdC5MZW5ndGggKyAyKmsgKyAxKQpzZXEge2xpc3QuTGVuZ3RoIC4uIGxpc3QuTGVuZ3RoICsgMiprfSB8PiBTZXEuaXRlciAoZnVuIGkgLT4gY2FjaGUuQWRkKGksICgwLCBbXSkpKQoKZm9yIGkgaW4gbGlzdC5MZW5ndGggLSAxIC4uIC0xIC4uIDAgZG8KICAgIGxldCBtYXhTdW0sIG1heExpc3QgPSAKICAgICAgICBzZXEge2kgKyBrIC4uIGkgKyAyKmt9CiAgICAgICAgfD4gU2VxLm1hcCAoZnVuIGkgLT4gY2FjaGUuW2ldKSAKICAgICAgICB8PiBTZXEubWF4QnkgZnN0CiAgICBjYWNoZS5BZGQoaSwgKGxpc3QuW2ldICsgbWF4U3VtLCBpIDo6IG1heExpc3QpKQoKbGV0IG1heFN1bSwgbWF4TGlzdCA9IHNlcSB7MCAuLiBrfSB8PiBTZXEubWFwIChmdW4gaSAtPiBjYWNoZS5baV0pIHw+IFNlcS5tYXhCeSBmc3QKcHJpbnRmbiAiJWk6ICVBIiBtYXhTdW0gbWF4TGlzdA==