How to solve Sherlock and Cost in C#

Hackerrank Link for this problem: https://www.hackerrank.com/challenges/sherlock-and-cost

When N = 2, S = S1 + max(|A2 - A1|), and S1 = 0 because there is not A0.
So now, a question is how to come up with all possible candiates of max(|A2 - A1|).

If A2 > A1 and depending on using 1 instead of A1, we have following:

1. A2 - 1(A1's minimum possible number) : e.g., if A1 = 3, A2 = 7, max(Abs(A2 - A1)) = 7-1 = 6
2. A2 - A1(A1's maximum possible number): e.g., if A1 = 3, A2 - 7, max(Abs(A2-A1)) = 7-3 = 4
3. Save S2[A2>A1] or S[0][1] = max (step1, step2);

If A2 <= A1 and depending on using 1 instead A2, we have following:

1. A1 - 1: becasue A1 > A2, one if best possible is Abs(A1 -1). e.g., if A1=7, A2=4, max = 7-1=6
2. 0: when A1 = A2.
3. Save S2[A2<=A1] or S[1][1] = max(step1, step2)

Now we have two possible solutions.

Therefore, When N= 2, the solution S is

S(N=2) = max(S[0][1], S[1][1])

Now, we consider N=3,

Basically, we repeat all consideration plus previous S2's solutions for each case such that

If A3 > A2,

1. S[1][1]  + A3 - 1 //using 1 case again
2. S[0][1]  + A3 - A2 // not using 1 case
3. Save S[0][2] = max(step1, step2)

If A3 <= A2

1. S[1][2] + A3 - 1 // using 1
2. S[0][2] + 0 // not using 1
3. Save S[1][2] = max(step1, step2)

Now once again, we have all possible solutions in {S[0][2], S[1][2]}

Therefore, When N= 3, the solution S is max(S[0][2], S[1][2])

From N= 2,3, we found following equation or pattern:

• If we run through to n -1, we collect all S[0][n-1] and S[1][n-1]
• And we can calculate S(n) = max(S[0][n-1], S[1][n-1]);

Ai and Ai-1 relationship	Using 1
Ai  > Ai-1	Yes	max	max
Ai  > Ai-1	No
Ai <= Ai-1	Yes	max
Ai <= Ai-1	No

And here is my C# implementation:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        var t = Int32.Parse(Console.ReadLine());
        for (int i = 0; i < t; i ++){
            var n = Int32.Parse(Console.ReadLine());
            var bi = Console.ReadLine().Split(new char[] {' '}).Select(c=> Int32.Parse(c)).ToArray();
            var result = GetCostS(n, bi);
            Console.WriteLine(result);
        }
    }
    static long GetCostS(int n,int[] bi){
        long[,] sum = new long[2,n];
        
        for(int i = 1; i < n; i++){
            sum[0,i] = Math.Max(sum[0,i-1] + Math.Abs(bi[i] - bi[i-1]), 
                                sum[1,i-1] + Math.Abs(bi[i] - 1));
            sum[1,i] = Math.Max(sum[0,i-1] + Math.Abs(bi[i-1] - 1), 
                                sum[1,i-1]);
        }
            
        return Math.Max(sum[0,n-1],sum[1,n-1]);
    }
}