C# || How To Find Longest Arithmetic Subsequence Of An Array Using C#
The following is a module with functions which demonstrates how to find the longest arithmetic subsequence of an array using C#.
1. Longest Arithmetic Subsequence Length – Problem Statement
Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.
Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length – 1, and that a sequence seq is arithmetic if seq[i+1] – seq[i] are all the same value (for 0 <= i < seq.length – 1).
Example 1:
Input: nums = [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: nums = [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
2. Longest Arithmetic Subsequence Length – Solution
The following is a solution which demonstrates how to find the longest arithmetic subsequence of an array.
The main idea in this solution is to maintain a dictionary map array of the differences seen at each index, where dp[index][diff] holds the frequency count at that index, for that specific diff.
Each item in the array is considered and checked against to their items to the left.
For each number (i,j) we determine the difference d = nums[i] – nums[j] and keep a count of the frequency the difference has been seen.
In the end, the max difference frequency is returned.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 22, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find longest arithmetic subsequence // ============================================================================ public class Solution { public int LongestArithSeqLength(int[] nums) { var result = 0; // Create a map array of size n var dp = new Dictionary<int, int>[nums.Length]; // Iterate the numbers in the array for (int i = 0; i < nums.Length; ++i) { // Create a new dictionary for this index dp[i] = new Dictionary<int, int>(); // Iterate over values to the left of i for (int j = 0; j < i; ++j) { // Get the difference between the two numbers var currentDiff = nums[i] - nums[j]; // Update the count matching the difference already seen from j for i dp[i][currentDiff] = (dp[j].ContainsKey(currentDiff) ? dp[j][currentDiff] : 0) + 1; // Keep track of the max difference count result = Math.Max(result, dp[i][currentDiff]); } } return result + 1; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
4
3
4
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
Leave a Reply