Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Write a C# code based on the blog I found on the internet - it takes time to figure out the algorithm.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TwoPointerTechniques
{
class Program
{
/// <summary>
/// Based on the code from the following blog:
/// https://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jsp
/// </summary>
/// <param name="args"></param>
static void Main(string[] args)
{
var sortedArr = new int[] { 1, 3, 4, 5, 7, 8, 9 };
var n = sortedArr.Length;
var lookup = FindArithmeticProgressionLength3(sortedArr);
}
/// <summary>
/// How to find if a sorted array contains an Arithmetic Progression (AP) of length 3?
/// </summary>
/// <param name="numbers"></param>
/// <returns></returns>
public static int[] FindArithmeticProgressionLength3(int[] numbers)
{
var n = numbers.Length;
var lookup = new int[n][];
for (int i = 0; i < n; i++)
{
lookup[i] = new int[n];
}
int maxAP = 2;
int apTerm = 0;
int apStart = 0;
// Any 2-letter series is an AP
// Here we initialize only for the last column of lookup because
// all i and (n-1) pairs form an AP of size 2
for (int i = 0; i < n; i++)
{
lookup[i][n - 1] = 2;
}
// Loop over the array and find two elements 'left' and 'right' such that
// numbers[left] + numbers[right] = 2 * numbers[middle]
for (int middle = n - 2; middle >= 1; middle--)
{
var left = middle - 1;
var right = middle + 1;
while (left >= 0 && right <= n - 1)
{
int isAP = (numbers[left] + numbers[right]) - 2 * numbers[middle];
if (isAP < 0)
{
right++;
}
else if (isAP > 0)
{
left--;
}
else
{
lookup[left][middle] = lookup[middle][right] + 1;
maxAP = Math.Max(maxAP, lookup[left][middle]);
if (maxAP == lookup[left][middle])
{
// Store the Arithmetic Progression's term
// And the start point of the AP
apTerm = numbers[middle] - numbers[left];
apStart = left;
}
right++;
left--;
}
}
}
return new int[]{ maxAP, apStart, apTerm };
}
}
}
/*
*
Test case analysis:
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Checking out 8
Found 7, 8, 9
lookup[4][5] = lookup[5][6] (2) + 1
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 3 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Checking out 7
Found 5, 7, 9
lookup[3][4] = lookup[4][6] (2) + 1
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
0 0 0 0 3 0 2
0 0 0 0 0 3 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Checking out 5
Found 3, 5, 7
lookup[1][3] = lookup[3][4] (3) + 1
Found 1, 5, 9
lookup[0][3] = lookup[3][6] (2) + 1
0 0 0 3 0 0 2
0 0 0 4 0 0 2
0 0 0 0 0 0 2
0 0 0 0 3 0 2
0 0 0 0 0 3 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Checking out 4
Found 3, 4, 5
lookup[1][2] = lookup[2][3] (0) + 1
Found 1, 4, 7
lookup[0][2] = lookup[2][4] (0) + 1
0 0 1 3 0 0 2
0 0 1 4 0 0 2
0 0 0 0 0 0 2
0 0 0 0 3 0 2
0 0 0 0 0 3 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Checking out 3
Found 1, 3, 5
lookup[0][1] = lookup[1][3] (4) + 1
0 5 1 3 0 0 2
0 0 1 4 0 0 2
0 0 0 0 0 0 2
0 0 0 0 3 0 2
0 0 0 0 0 3 2
0 0 0 0 0 0 2
0 0 0 0 0 0 2
Max AP length = 5
1, 3, 5, 7, 9,
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment