fork download
copy 
  1. let rand =
  2.     let randGen = System.Random()
  3.     fun _ -> randGen.Next 300
  4.  
  5. let [<Literal>] ListSize = 100000
  6.  
  7. let k = 3
  8. let list = Array.init ListSize rand 
  9. printfn "%A" list
  10.  
  11. let cache = System.Collections.Generic.Dictionary (list.Length + 2*k + 1)
  12. seq {list.Length .. list.Length + 2*k} |> Seq.iter (fun i -> cache.Add(i, (0, [])))
  13.  
  14. for i in list.Length - 1 .. -1 .. 0 do
  15.     let maxSum, maxList = 
  16.         seq {i + k .. i + 2*k}
  17.         |> Seq.map (fun i -> cache.[i]) 
  18.         |> Seq.maxBy fst
  19.     cache.Add(i, (list.[i] + maxSum, i :: maxList))
  20.  
  21. let maxSum, maxList = seq {0 .. k} |> Seq.map (fun i -> cache.[i]) |> Seq.maxBy fst
  22. printfn "%i: %A" maxSum maxList
Success #stdin #stdout 0.23s 38972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[|71; 258; 45; 83; 163; 99; 200; 273; 8; 8; 122; 34; 147; 40; 148; 253; 78; 289;
  190; 129; 229; 134; 31; 70; 101; 56; 202; 229; 138; 104; 181; 225; 299; 156;
  187; 176; 158; 253; 124; 233; 290; 147; 198; 197; 190; 185; 15; 40; 112; 236;
  23; 37; 11; 270; 75; 237; 226; 275; 281; 106; 197; 270; 135; 203; 126; 197; 34;
  290; 152; 272; 95; 124; 165; 256; 139; 82; 235; 134; 180; 215; 41; 162; 117;
  201; 81; 143; 213; 29; 81; 250; 249; 183; 271; 18; 36; 19; 12; 294; 70; 292;
  ...|]
6330275: [1; 4; 7; 10; 14; 17; 20; 24; 27; 31; 34; 37; 40; 43; 46; 49; 53; 58; 61; 64; 67;
 70; 73; 76; 79; 83; 86; 89; 92; 97; 100; 103; 106; 109; 112; 116; 119; 122; 125;
 128; 131; 134; 137; 140; 144; 147; 150; 153; 156; 159; 164; 167; 171; 175; 178;
 181; 184; 187; 191; 195; 198; 201; 204; 207; 211; 214; 217; 220; 224; 228; 232;
 235; 238; 243; 246; 250; 253; 256; 259; 262; 265; 268; 272; 275; 278; 281; 285;
 289; 292; 295; 298; 301; 304; 307; 310; 313; 316; 319; 323; 326; ...]
https://ideone.com/tCl2WO
language:
F# (mono 4.1)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!