title: Maximum sum of n intervals in a sequence
body: <p>I'm doing some programming "kata" which are skill building exercises for programming (and martial arts). I want to learn how to solve for algorithms like these in shorter amounts of time, so I need to develop my knowledge of the patterns. Eventually I want to solve in increasingly efficient time complexities (O(n), O(n^2), etc), but for now I'm fine with figuring out the solution with any efficiency to start.</p>
  
  <p><strong>The problem:</strong></p>
  
  <p>Given arr[10] = [4, 5, 0, 2, 5, 6, 4, 0, 3, 5]</p>
  
  <p>Given various segment lengths, for example one 3-length segment, and two 2-length segments, find the optimal position of (or maximum sum contained by) the segments without overlapping the segments.</p>
  
  <p>For example, solution to this array and these segments is 2, because:</p>
  
  <p>{4 5} 0 2 {5 6 4} 0 {3 5}</p>
  
  <p><strong>What I have tried before posting on stackoverflow.com:</strong></p>
  
  <p>I've read through:</p>
  
  <p><a href="https://stackoverflow.com/questions/24026073/algorithm-to-find-maximum-coverage-of-non-overlapping-sequences-i-e-the-weig">Algorithm to find maximum coverage of non-overlapping sequences. (I.e., the Weighted Interval Scheduling Prob.)</a></p>
  
  <p><a href="https://stackoverflow.com/questions/4593583/algorithm-to-find-longest-non-overlapping-sequences">algorithm to find longest non-overlapping sequences</a></p>
  
  <p>and I've watched MIT opencourseware and read about general steps for solving complex problems with dynamic programming, and completed a dynamic programming tutorial for finding Fibonacci numbers with memoization. I thought I could apply memoization to this problem, but I haven't found a way yet.</p>
  
  <p>The theme of dynamic programming is to break the problem down into sub-problems which can be iterated to find the optimal solution.</p>
  
  <p>What I have come up with (in an OO way) is</p>
  
  <pre><code>foreach (segment) {
      - find the greatest sum interval with length of this segment
  </code></pre>
  
  <p>This produces incorrect results, because not always will the segments fit with this approach. For example:</p>
  
  <p>Given arr[7] = [0, 3, 5, 5, 5, 1, 0] and two 3-length segments,</p>
  
  <p>The first segment will take 5, 5, 5, leaving no room for the second segment. Ideally I should memoize this scenario and try the algorithm again, this time avoiding 5, 5, 5, as a first pick. <strong>Is this the right path</strong>?</p>
  
  <p>How can I approach this in a "dynamic programming" way?</p>