<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. You have to partition the array into one or more <strong>contiguous</strong> subarrays.</p>

<p>We call a partition of the array <strong>valid</strong> if each of the obtained subarrays satisfies <strong>one</strong> of the following conditions:</p>

<ol>
	<li>The subarray consists of <strong>exactly</strong> <code>2,</code> equal elements. For example, the subarray <code>[2,2]</code> is good.</li>
	<li>The subarray consists of <strong>exactly</strong> <code>3,</code> equal elements. For example, the subarray <code>[4,4,4]</code> is good.</li>
	<li>The subarray consists of <strong>exactly</strong> <code>3</code> consecutive increasing elements, that is, the difference between adjacent elements is <code>1</code>. For example, the subarray <code>[3,4,5]</code> is good, but the subarray <code>[1,3,5]</code> is not.</li>
</ol>

<p>Return <code>true</code><em> if the array has <strong>at least</strong> one valid partition</em>. Otherwise, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,4,4,5,6]
<strong>Output:</strong> true
<strong>Explanation:</strong> The array can be partitioned into the subarrays [4,4] and [4,5,6].
This partition is valid, so we return true.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no valid partition for this array.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
public:
    bool validPartition(vector<int>& nums) {
        if(nums.size() == 2) return nums[0] == nums[1];
        
        bool dp_i_3 = true;
        bool dp_i_2 = false;
        bool dp_i_1 = nums[0] == nums[1];
        for(int i = 3 ; i <= nums.size() ; i++)
        {
            // case 1 : if the last 2 elements are a good subarray and previous i - 2 are valid
            bool dp_i = (nums[i-1] == nums[i-2]) && dp_i_2;

            // case 2 : last 3 are equal
            if(!dp_i) dp_i = i > 2 && (nums[i-1] == nums[i-2]) && nums[i-2] == nums[i-3] && dp_i_3;

            // case 3 : last 3 are consecutive
            if(!dp_i) dp_i = i > 2 && (nums[i-1] == nums[i-2] + 1) && (nums[i-2] == nums[i-3] + 1) && dp_i_3;

            dp_i_3 = dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
            if(!(dp_i_3 || dp_i_2 || dp_i_1)) return false;
        }
        return dp_i_1;
    }
};
86300