C++ O(n) solution using Kadane's Algorithm


#1

The basic approach is
We can get x1-x4 from (x1-x2)+(x2-x3)+(x3-x4)

So we just need to store the differences of consecutive elements and find max sum subarray + length

int Solution::maxArr(vector &A) {
int n = A.size();
vector diff;
for(int i=1;i<n;i++){
diff.push_back(A[i-1]-A[i]);
}
int best=1,curr=0;
int len=1;
for(int i=0;i<n-1;i++){
curr=curr+diff[i]+1;
best = max(best,curr);
if(curr<0){
curr=0;
len=1;
}else{
len++;
}
}
//cout<<"best is "<<best<<endl;
for(int i=0;i<n-1;i++)
diff[i]=diff[i]*-1;
len=1;
curr=0;
for(int i=0;i<n-1;i++){
curr=curr+diff[i]+1;
// cout<<"curr is "<<curr<<endl;
best = max(best,curr);
if(curr<0){
curr=0;
len=1;
}else{
len++;
}
}
//cout<<"best is "<<best<<endl;
return best;
}


#2

are we assuming all elements in the array are distinct?


#3

No we are not assuming that

If 2 elements are equal then also x1-x4 can be written as (x1-x2) + (x2-x3) + (x3-x4)
That is sum of adjacent differences irrespective of wether x1=X2 or not


#4

Nice approach but Where did the mod go ?


#5

Due to mod only I am checking for both positive and negative cases


#6

When I am doing diff[I]=diff[I]*-1


#7

How is the “len” variable being used?