Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/3ecd40451f2ad65e44ed6c8d7f4a09d4 to your computer and use it in GitHub Desktop.
Save jianminchen/3ecd40451f2ad65e44ed6c8d7f4a09d4 to your computer and use it in GitHub Desktop.
Array of array products - dynamic programming algorithm - I got advice to declare variable leftToRight first, and then switch order of two statements of line 22 and line 24.
using System;
class Solution
{
public static int[] ArrayOfArrayProducts(int[] arr)
{
if(arr == null || arr.Length < 2)
return new int[0];
var length = arr.Length;
var product = new int[length];
for(int i = 0; i < length; i++)
{
product[i] = 1;
}
var leftToRight = 1;
// left to right, one multiplication
for(int i = 0; i < length; i++)
{
product[i] = leftToRight;
leftToRight *= arr[i];
}
// right to left, two multiplication
var rightToLeft = 1;
for(int i = length - 1; i >=0 ; i--)
{
product[i] *= rightToLeft;
rightToLeft *= arr[i];
}
return product;
}
static void Main(string[] args)
{
}
}
/*
dynamic programming
iteration -> left to right
product[]
for iteration
one multiplication
product[0] = 1
8, 10, 2
*8 *10
second iteration from right to left
for each iteration
two mulitiplcations
product[i] *= arr[i + 1] - two mulitiplcations
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment