State transition approach


#1

Check out this state transition approach.
int Solution::maxProfit(const vector &arr) {
int n = arr.size();
int s0 = 0 , s1 = -arr[0] , s2 = INT_MIN , s3 = INT_MIN , s4 = INT_MIN;
for(int i = 1; i < n ; i++){
int t0 = s0 , t1 = s1 , t2 = s2 , t3 =s3 , t4 = s4;
s1 = max(s1 , s0-arr[i]);
s2 = max(s2 , s1+arr[i]);
s3 = max(s3 , s2-arr[i]);
s4 = max(s4 , s3+arr[i]);
}
return max(s0 , max(s2 , s4));
}