public class MaxSubArraySum
    {
        public int MaxSequence(int[] arr)
        {
            var table = new int[arr.Length, arr.Length];

            int max = 0;

            // init diag
            for (int i = 0; i < arr.Length; i++)
            {
                table[i, i] = arr[i];

                if (table[i, i] > max)
                {
                    max = table[i, i];
                }
            }

            for (int i = 0; i < arr.Length; i++)
            {
                for (int j = i; j < arr.Length; j++)
                {
                    if (j != i)
                    {
                        table[i, j] = table[i, j - 1] + arr[j];

                        if (table[i, j] > max)
                        {
                            max = table[i, j];
                        }
                    }
                }
            }

            return max;
        }
    }