Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Prototype the algorithm of Maximum disjoint subtree product using an array first. May 31, 2018
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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.