# Concise (24 lines) C++ Greedy/DP solution with detailed explanation

• DP:

Let f(i) be the number of consecutive integers at index i,

Transition equation and example:

``````f(i) = min {f(j)} + 1,   if j<i && nums[i]==nums[j]+1
1                 ,   o.w.
``````

This means that for nums[i], we look at all nums[j] with j<i and nums[i] == nums[j] + 1, and we select the nums[j] whose f(j) is the smallest to concatenate with nums[i] (this is why f(i) = min {f(j)} + 1)

Note that since each number in the array can only be concatenated once, we have to mark a nums[j] as 'used' once it has been selected to concatenate with a nums[i]. This solution is Greedy since for each nums[i], we select the minimum value of f(j)'s from all j's with nums[i] == nums[j]+1, and once we select one nums[j] we mark it as used and never consider it again (so it is some knid of local optima).

The intuition behind the Greedy solution is that we try to complete a subsequence with shorter length first, for example,

``````nums  1 2 3 3 4 4 5 5
f     1 2 3 1 2 4 3 5
``````

For the first nums[i]==4, we select the one with f[j]==1 instead of the one with f[j]==3 to concatenate since the one with f[j]==1 is the shortest among the two.

Note that to see if the array can be split into subsequences, we keep a global integer 'count'. Whenever you get an f(i)==3, it means we have got a subsequence of length 3, so you can add 3 to count. And whenever you get an f(i)>3, it means you get an additional element concatenated to a subsequence with length >=3, so you only add 1 to count (since all previous has been added to count).

In the end, if count == nums.size(), return true since all elements in the array are in some subsequence with length >= 3. Otherwise, return false.

``````class Solution {
public:
bool isPossible(vector<int>& nums) {
vector<int> f(nums.size(),1);
vector<bool> used(nums.size(),false);
int count = 0;
for(int i=0; i<nums.size(); i++) {
int j = i-1, index = -1, fvalue = INT_MAX;
while(j>=0 && (nums[i]==nums[j] || nums[i]==nums[j]+1)) {
if(nums[i]==nums[j]+1 && !used[j]) {
if(f[j]<fvalue) {
index=j;
fvalue=f[j];
}
}
j--;
}
if(index!=-1) {
used[index]=true;
f[i] = f[index]+1;
if(f[i]==3) count+=3;
else if(f[i]>3) count++;
}
}
return count==(int)nums.size();
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.