Правильное и эффективное решение задачи на дп

void Main()
{
    
    int size = 10000000;
    var rnd = new Random();
    int k = 10;
    int minp = 10, maxp = 20;
    var m = new int[size];
    for(int i = 1; i < size; i++) m[i] = m[i-1] + 1 + rnd.Next(k); 
    var p = new int[size];
    for(int i = 0; i < size; i++) p[i] = rnd.Next(minp, maxp); 
    //Console.WriteLine("m = {0}", string.Join(", ", m));
    //Console.WriteLine("p = {0}", string.Join(", ", p));
    
    var timer = new Stopwatch();
    timer.Start();
    var res = CalculateProfit(m, p, k, false); 
    timer.Stop();
    Console.WriteLine("{0} ({1} ms)", res, timer.ElapsedMilliseconds);
}
 
private static int CalculateProfit(int[] m, int[] p, int k, bool isPrint = false)
{
    var maxp = p.Max(); // используем для отсечения
    var s = new int[m.Length]; 
    for(int j = m.Length-1; j >= 0; j--)
    {
        for(int i = j; i < m.Length; i++)
        {
            var res = p[i];
            var nextpos = i + 1; 
            while(nextpos < m.Length && m[nextpos] - m[i] < k) nextpos++;
            if(nextpos < m.Length) res += s[nextpos];
            if(res > s[j])
                s[j] = res;
            else if(res + maxp < s[j])
                break;
        }
        if(isPrint) Console.WriteLine(string.Join(", ", s));
    }
    return s[0];
}

private static int CalculateProfit2(int[] m, int[] p, int k, bool isPrint = false)
{
    var s = new int[m.Length]; 
    s[m.Length-1] = p[m.Length-1];
    int nextpos = m.Length;
    for(int j = m.Length-2; j >= 0; j--)
    {
        var res = p[j];
        while(m[nextpos-1] - m[j] >= k) 
            nextpos--;
        if(nextpos < m.Length) 
            res += s[nextpos];
        s[j] = Math.Max(res, s[j+1]);       
        if(isPrint) Console.WriteLine(string.Join(", ", s));
    }
    return s[0];
}

private static int CalculateProfit3(int[] m, int[] p, int k, bool isPrint = false)
{
    var s = new int[m.Length+1]; 
    s[m.Length-1] = p[m.Length-1];
    int nextpos = m.Length;
    for(int j = m.Length-2; j >= 0; j--)
    {
        while(m[nextpos-1] - m[j] >= k) 
            nextpos--;
        s[j] = Math.Max(p[j] + s[nextpos], s[j+1]);       
        if(isPrint) Console.WriteLine(string.Join(", ", s));
    }
    return s[0];
}