title: Finding max sum contiguous subarray when atmost k elements can be omitted?
body: <p>Eg- <code>n=10</code><br>
  <code>arr[]={6,-5,3,-7,6,-1,10,-8,-8, 8}</code><br>
  <code>For k=0, best segment is 5-7 with sum=15.
  For k=2, best segment is 1-7 with sum=24.
  For k=6, best segment is 1-10 with sum=33.</code><br>
  Given array and k, find sum.</p>
  
  <p>I think, let <code>dp[i][j]</code> denote the maximum segment ending at position i with at most j elements dropped. Inductively compute <code>dp[i][j]</code>from <code>dp[i][j-1]</code>. But how to keep track of elements removed from <code>dp[i][j-1]</code> and not to remove them again??? I am confused in dp problems. I want to know dp approach and some other approach if possible?</p>