Arithmetic Slices II - Subsequence

Problem Statement

In the given task, we are presented with an integer array called nums, and our aim is to determine the total number of subsequences within this array that qualify as arithmetic sequences. To be defined as arithmetic, a series must include at least three numbers where the difference between any successive pairs remains consistent across the sequence.

For instance, sequences such as [1, 3, 5, 7, 9] and [7, 7, 7, 7] meet the criteria as each maintains a fixed difference between elements, whether that difference is positive, negative, or zero. In contrast, a sequence like [1, 1, 2, 5, 7] doesn't qualify due to varying differences between successive values.

Further elaboration includes understanding the concept of a subsequence, which unlike subsequents, allows the exclusion (but not rearrangement) of certain elements from the parent array to form a new sequence. For example, [2,5,10] is a valid subsequence extracted from a larger array [1,2,1,2,4,1,5,10].

Given the constraints specified, the task guarantees that the result will fit within a 32-bit integer, emphasizing efficiency in handling potentially large datasets.

Examples

Example 1

Input:

nums = [2,4,6,8,10]

Output:

7

Explanation:

All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Example 2

Input:

nums = [7,7,7,7,7]

Output:

16

Explanation:

Any subsequence of this array is arithmetic.

Constraints

• 1  <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1

Approach and Intuition

To tackle the problem of counting all arithmetic subsequences in the array nums, one can utilize a methodical and analytical approach:

1. Understand the variable properties of an arithmetic sequence:

   • It must contain no less than three elements.
   • The difference, or common ratio d, between consecutive elements must remain constant.

2. Conceptually, to identify and count these subsequences, a viable approach is using a dynamic programming technique paired with the utilization of a hashmap or dictionary to keep track of potential arithmetic differences and their frequency at each element in the array.

3. As you iterate through the array:

   • For each element nums[j], consider it as a possible end element of an arithmetic subsequence.
   • For every preceding element nums[i] where i < j, calculate the difference d = nums[j] - nums[i].
   • Using a hashmap, record how often each difference d occurs up to position j.
   • If a specific difference d has been encountered before at a preceding position, it indicates potential extensions to previous subsequences, contributing to new subsequences ending at j.

4. Implement a running count of subsequences as you progress through the list which, eventually, when the array is wholly parsed, yields the total count of valid arithmetic subsequences.

By applying this guided approach using dynamic programming concepts paired with effective hash mapping to categorize and count subsequences based on their common ratio of differences, it facilitates an efficient solution to the problem given the constraints outlined.

Solutions

#define LONG long long
class Solution {
public:
    int findArithmeticSlices(vector<int>& nums) {
        int length = nums.size();
        LONG total = 0;
        vector<map<LONG, int>> count(length);
        for (int current = 1; current < length; current++) {
            for (int prev = 0; prev < current; prev++) {
                LONG difference = (LONG)nums[current] - (LONG)nums[prev];
                int sequenceCount = 0;
                if (count[prev].find(difference) != count[prev].end()) {
                    sequenceCount = count[prev][difference];
                }
                count[current][difference] += sequenceCount + 1;
                total += sequenceCount;
            }
        }
    
        return (int)total;
    }
};