โจทย์จริงของเนื้อหานี้คือ Arithmetic Slices** (Title "Remove K Digits" ผิดพลาด เนื้อหาเป็น Arithmetic Slices)
ให้ Array A หาจำนวน **Arithmetic Slices** คือ Subarray ความยาว ≥ 3 ที่ **ความต่างระหว่าง Adjacent Elements คงที่**
ตัวอย่าง
A = [1,2,3,4]
Arithmetic Slices: [1,2,3], [2,3,4], [1,2,3,4] -> 3 Slices
แนวทาง: DP (Dynamic Programming)
dp[i] = จำนวน Arithmetic Slices ที่ **ลงท้ายที่ Index i** (และมีความยาว ≥ 3)
- ถ้า
A[i] - A[i-1] == A[i-1] - A[i-2](รักษา Common Difference): - ทุก Slice ที่ลงท้าย i-1 สามารถต่อยอดมาที่ i ได้ (+1 Slice ใหม่คือ [i-2, i-1, i])
dp[i] = 1 + dp[i-1]- สะสมคำตอบ
ret += dp[i]
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ret = 0;
int n = A.size();
vector<int> dp(n, 0);
for (int i = 2; i < n; i++) {
if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
dp[i] = 1 + dp[i-1];
ret += dp[i];
}
}
return ret;
}
};
Input / Output
Input: [1,2,3,4] Output: 3
ความซับซ้อน (Complexity)
- Time: O(N)
- Space: O(N) (ลดเหลือ O(1) ได้โดยเก็บแค่ dp_prev)
หมายเหตุ
Title ใน XML เขียนว่า "Remove K Digits" แต่โค้ดและเนื้อหาเป็น **Arithmetic Slices** ครับ ขอแก้ไข Title ให้ตรงกับเนื้อหาจริง
