Prototype the algorithm of Maximum disjoint subtree product using an array first. May 31, 2018

TwoDisjointSubarrayMaximumProduct.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TwoDisjointSubarrayMaximumProduct
{
    /// <summary>
    /// Given an integer array, find two disjoint subarray maximum product. 
    /// This is the subproblem of hard level algorithm of Maximum disjoint subtree product
    /// https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximum-disjoint-subtree-product
    /// 
    /// May 31, 2018
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            RunTestSubRoutine1();
            RunTestSubRoutine2();
        }

        public static void RunTestSubRoutine1()
        {
            var result = GetSubarrayWithMaximumMinimumWithStartIndex(new int[]{2, -1}); 
        }

        public static void RunTestSubRoutine2()
        {
            var result = GetSubarrayWithMaximumMinimumWithEndIndex(new int[] { 2, -1 }); 
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static int[] getSubarrayWithMaximumMinimumMinimumStart(int[] numbers)
        {
            var maxMin = GetSubarrayWithMaximumMinimumWithStartIndex(numbers); 

            // preprocessing, apply another dynamic programming algorithm
            // will come back later on
            return new int[0]; 
        }

        /// <summary>
        /// May 31, 2018
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        public static int FindTwoDisjointSubarrayMaximumProduct(int[] numbers)
        {
            return 0; 
        }

        /// <summary>
        /// code review May 31, 2018
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        private static int[,] GetSubarrayWithMaximumMinimumWithEndIndex(int[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return new int[0, 0];
            }

            var length = numbers.Length;
            var maxMin = new int[length, 2];

            for (int index = 0; index < length; index++)
            {                
                var current = numbers[index];
                
                if (index == 0)
                {
                    maxMin[index, 0] = numbers[index];
                    maxMin[index, 1] = numbers[index];
                }
                else
                {
                    // 0 - max, 1 - min
                    var left = index - 1;
                    var leftMax = maxMin[left, 0];
                    var leftMin = maxMin[left, 1];

                    var options = new int[] { current, current + leftMax, current + leftMin };

                    maxMin[index, 0] = options.Max();
                    maxMin[index, 1] = options.Min();
                }
            }

            return maxMin;
        }

        /// <summary>
        /// code review on May 31, 2018
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        private static int[,] GetSubarrayWithMaximumMinimumWithStartIndex(int[] numbers)
        {
            if (numbers == null || numbers.Length == 0)
            {
                return new int[0, 0];
            }

            var length = numbers.Length;
            var maxMin = new int[length, 2];

            for (int index = 0; index < length; index++)
            {
                var visit = length - index - 1;
                var current = numbers[visit];

                var visitLastOne = index == 0;
                if (visitLastOne)
                {
                    maxMin[visit, 0] = numbers[visit];  
                    maxMin[visit, 1] = numbers[visit];  
                }
                else
                {
                    // 0 - max, 1 - min
                    var right = visit + 1;
                    var rightMax = maxMin[right, 0];
                    var rightMin = maxMin[right, 1];

                    var options = new int[] { current, current + rightMax, current + rightMin };
                    maxMin[visit, 0] = options.Max();
                    maxMin[visit, 1] = options.Min(); 
                }
            }

            return maxMin; 
        }
    }
}