Sponsored
Sponsored
This approach uses dynamic programming and hashmaps to calculate arithmetic subsequences efficiently. For each index, we maintain a hashmap that tracks the count of different differences (arithmetic differences) and the number of subsequences that end with that difference at the given index. This allows us to build potential subsequences as we iterate over the array.
Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n * m), where m is the number of possible differences (limited by the constraint of 31-bit integer).
1using System;
2using System.Collections.Generic;
3
4class ArithmeticSlices {
5 public static int NumberOfArithmeticSlices(int[] nums) {
6 int total = 0;
7 int n = nums.Length;
8 var dp = new Dictionary<long, int>[n];
9
10 for (int i = 0; i < n; i++) {
11 dp[i] = new Dictionary<long, int>();
12 for (int j = 0; j < i; j++) {
13 long diff = (long)nums[i] - (long)nums[j];
14 dp[i].TryGetValue(diff, out int endCount); // Existing count
15 dp[j].TryGetValue(diff, out int countAtJ);
16 dp[i][diff] = endCount + countAtJ + 1;
17 total += countAtJ;
18 }
19 }
20 return total;
21 }
22
23 static void Main() {
24 int[] nums = {2, 4, 6, 8, 10};
25 Console.WriteLine(NumberOfArithmeticSlices(nums));
26 }
27}This C# solution uses an array of dictionaries where each dictionary tracks the number of arithmetic subsequences ending at each index with a particular difference. For each pair of indices `(j, i)`, the difference is computed and the count of arithmetic subsequences is updated.
This approach considers all possible subsequences (using combinations) and checks if each subsequence is arithmetic. Although not efficient, it can be used to demonstrate the logic on small arrays to understand the problem better.
Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.
1
This JavaScript function recursively forms all possible combinations of subsequences. Each subsequence is checked for arithmetic properties, and results are stored incrementally. It's intended more for understanding rather than performance given its complexity.