最长等差数列 - 中等难度

*************

C++

TITLE: 1027. 最长等差数列 - 力扣（LeetCode）

*************

see the topic:

she is similar with 1218. 最长定差子序列 - 力扣（LeetCode） ,see, the only difference is the difference, haha, punny.

 Use another language is not a EZ thing, but I have to learn it cuz I want.

*************

I had really bad weekend and totally donot wnat it any more.

Still some good news for me that my new keyboard works well. 

I donnot want to talk too much an bout the bad things and time to work. So back to the topic angin.

What should I do? I think aesthetics of violence always works.

The first step is collecting all the possible combinations.

The second step is that determine if each group is an equal variance seris.

The last is return dp[n].

When talks about dp array, define dp[i] is the longest equal variance seris when the pointer comes to the i place.

Take an example:

I am have a special memory of get the size of sring or a number or an array, I can read the numbers grtting the size. if the array has only two elements and of course it is the arithmetic progression.

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // get the size
        if (n < 2) return n; // two elements always work
        
       
    }
};

initialise a max length, at least 2 elements, it is obviously that series made up of at least 2 elements and that is why the initial is 2.

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // get the size
        if (n < 2) return n; // two elements always work
        
        int max_len = 2; // initialise the max length
        
    }
};

and then I need a space to store the series, 

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // get the size
        if (n < 2) return n; // two elements always work
        
        int max_len = 2; // initialise the max length

        vector<int> current_subseq; // to store the series which is being checked

      
    }
};

to have a better reading, iddentify a way to generate all possible  units.

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // get the size
        if (n < 2) return n; // two elements always work
        
        int max_len = 2; // initialise the max length

        vector<int> current_subseq; // to store the series which is being checked

        // generate all possible units and return the max length
        generateSubsequences(0, current_subseq, nums, max_len);
        return max_len;
    }
    
    // the way to check if the seris is the arithmetic seris
private:
    bool isArithmetic(vector<int>& seq) {
        if (seq.size() < 2) return false;

        
       
    }
};

today write a really small staff, and go to play some balls minites later. so maybe writer later in the evining.

*************

Write nothing in the evening and such a unpleasent times.

For somereason I am out of order and have to reach my inner peace.

Still its a sunny day and the sunshine always makes me happy.

Come on, a fucking new day is coming just enjoy it.

back to the code which is differcult, after check the seris is arithmetic, find a way check.

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // get the size
        if (n < 2) return n; // two elements always work
        
        int max_len = 2; // initialise the max length

        vector<int> current_subseq; // to store the series which is being checked

        // generate all possible units and return the max length
        generateSubsequences(0, current_subseq, nums, max_len);
        return max_len;
    }
    
    // the way to check if the seris is the arithmetic seris
private:
    bool isArithmetic(vector<int>& seq) {
        if (seq.size() < 2) return false;

        
        int d = seq[1] - seq[0];
        for (int i = 2; i < seq.size(); i++) {
            if (seq[i] - seq[i - 1] != d) {
                return false;
            }
        }
        return true;
    }
    
    
    }
};

things behind I cannot tell so just paste the code here. 

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 公共方法，用于计算最长等差数列的长度
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size(); // 获取数组的长度
        if (n < 2) return n; // 如果数组长度小于2，直接返回长度，因为无法形成等差数列
        
        int max_len = 2; // 初始化最长等差数列长度为2，因为至少需要两个元素
        vector<int> current_subseq; // 用于存储当前子序列
        generateSubsequences(0, current_subseq, nums, max_len); // 生成所有可能的子序列
        return max_len; // 返回最长等差数列的长度
    }
    
private:
    // 检查给定序列是否为等差数列
    bool isArithmetic(vector<int>& seq) {
        if (seq.size() < 2) return false; // 如果序列长度小于2，不是等差数列
        int d = seq[1] - seq[0]; // 计算等差数列的公差
        for (int i = 2; i < seq.size(); i++) { // 从第三个元素开始检查
            if (seq[i] - seq[i - 1] != d) { // 如果当前元素与前一个元素的差不等于公差
                return false; // 不是等差数列
            }
        }
        return true; // 所有元素的差都等于公差，是等差数列
    }
    
    // 递归生成所有可能的子序列，并检查是否为等差数列
    void generateSubsequences(int index, vector<int>& current_subseq, vector<int>& nums, int& max_len) {
        if (index == nums.size()) { // 如果索引等于数组长度，结束递归
            return;
        }
        // 不选择当前元素，继续生成子序列
        generateSubsequences(index + 1, current_subseq, nums, max_len);
        // 选择当前元素，将其添加到当前子序列中
        current_subseq.push_back(nums[index]);
        // 如果当前子序列长度至少为2，检查是否为等差数列
        if (current_subseq.size() >= 2) {
            if (isArithmetic(current_subseq)) { // 如果是等差数列
                if (current_subseq.size() > max_len) { // 如果当前子序列长度大于已知最长长度
                    max_len = current_subseq.size(); // 更新最长长度
                }
            }
        }
        // 继续生成子序列，包括当前元素
        generateSubsequences(index + 1, current_subseq, nums, max_len);
        // 从当前子序列中移除最后一个元素，回溯
        current_subseq.pop_back();
    }
};

Guess the code works but it runs so slow.

Need a smart one to work it out.

Something bad happened last nigit I drove home. There was an idiot shit drove acrross two lines and suddenly in front of my car and of course I greated him CNM, another C language, and he knock my car glasses and greated me too, unfortunately, I lost my strong attitude, what a fuck.

I have to use a samrt code to solve the topic I do remember a friend dp.

Define dp[i][d], in the position i, store the length of commin difference d. For each position i,  need to look at all the positions j in front of it, compute the difference d = nums[i] - nums[j], and then see if there is any information about the difference d in dp[j]. If there is, then dp[i][d] = dp[j][d] + 1; if there isn't, then dp[i][d] = 2, since there are at least two numbers, nums[j] and nums[i].

for example:

i = 0, nums[0] = 3, dp[0] = 0;

i = 1, nums[1] = 6, j = 0, d = 6 - 3 = 3, dp[1][3] = 2;

i = 2, nums[2] = 9, j = 0, d = 9 - 3 = 6, dp[2][6] = 2,

                              j = 1, d = 9 - 6 = 3, dp[1][3] = 3, so dp[2][3] = dp[1][3] + 1 = 3;

i=3，nums[3]=12, j=0，d=12-3=9，dp[0] has no d=9，so dp[3][9]=2;

                              j=1，d=12-6=6，dp[1] has no d=6，so dp[3][6]=2;

                              j=2，d=12-9=3，dp[2] do have d=3，dp[2][3]=3，so dp[3][3]=3+1=4;

In sumary，

dp[0] is empty

dp[1]: {3:2}

dp[2]: {6:2, 3:3}

dp[3]: {9:2, 6:2, 3:4}

the maxumin length is 4，code works。

And talk to the computer how to understand my order.

dp use unordered_map<int, int>. rember the undered_map? I used in the topics, map is a key-value pairs, and based on hash, here is the standard form：

unordered_map<key_type, value_type> map_name;

 the usage of the map is:

map_name[key] = value; // insert

// find
if (map_name.find(key) != map_name.end()) {
    // 键存在，可以访问 map_name[key]
}

// visit, if the key doesnot exist, it will insert a new key
map_name[key];


// delete
map_name.erase(key);

// and travel the hash
for (auto it = map_name.begin(); it != map_name.end(); ++it) {
    std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}

so there is the spark:

Define a dynamic planning array: Use an array dp, where dp[i] is a hash table recording the lengths of equidistant subsequences at position i, ending with different differences d.

Initialization: Set a variable max_len to record the length of the currently found longest isochronous subsequence, with an initial value of 2 (since the shortest isochronous subsequence length is 2).

Dynamic Programming Process: Iterate through the array nums, for each position i, and then iterate through all the positions j before it, calculate the difference d = nums[i] - nums[j].

If dp[j] contains the difference d, then dp[i][d] = dp[j][d] + 1, otherwise dp[i][d] = 2.

Update max_len to be the maximum value of dp[i][d].

Boundary case: If the length of the array is less than 2, return the length of the array directly.

and the code is easy to write:

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        
        // dp[i] is a hash map that records the length of arithmetic sequences ending at i with difference d
        vector<unordered_map<int, int>> dp(n);
        
        int max_len = 2; // At least two elements in the sequence
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = nums[i] - nums[j];
                // If there is a sequence ending at j with difference d, extend it
                if (dp[j].count(d)) {
                    dp[i][d] = dp[j][d] + 1;
                } else {
                    // Start a new sequence with difference d
                    dp[i][d] = 2;
                }
                // Update the maximum length found
                if (dp[i][d] > max_len) {
                    max_len = dp[i][d];
                }
            }
        }
        
        return max_len;
    }
};

Wish we all have healthy body and relationship.