C++ : Longest Arithmetic Subarray

Question

Given an input array, the output must be the length of the longest arithmetic subarray of the given array.

I am getting a different output other than the desired one. I don't understand where I went wrong, I'm still a beginner so please ignore the rookie mistakes and kindly help me out wherever I'm wrong. Thanks in advance.

Here's the code:


#include <iostream>

using namespace std;

int main () {
    int n;
    cin>>n;
    int array[n];
    for (int i=0;i<n;i++)
  {
        cin>>array[i];
    }
    
    int length = 2;
    int cd = array[1] - array[0];
    for(int i=2; i<n; i++){
        if(array[i] - array[i-1] == cd){
            length++;
        }
        else {
            cd = array[i] - array[i-1];
            length=2;
        }
        cout<<length<<" ";
    }
    return 0;
}

Also, you should be maintaining the maximum length. You are resetting it every time you reach an else statement. — EuxhenH, Nov 21 '21 at 07:33

score 0 · Answer 1 · answered Nov 21 '21 at 07:39

If you are looking for a subsequence then what you did would not accomplish that.

For example:

Input: nums = [9,4,7,2,10]
Output: 3
Explanation: 
The longest arithmetic subsequence is [4,7,10].

You would require a nested loop structure (a for loop within the for loop you currently have) to accomplish that as you want to check a certain cd with the entire array and not just the next element.

If you require to find a subsequence/subarray given that the elements must be adjacent to one another then your program would work correctly.

Also a big error in your code is that you are printing the length inside the for loop. Unsure of whether that was for debugging purposes.

score 0 · Answer 2 · answered Nov 21 '21 at 07:51

The problem here is you're resetting length after every update. You need a variable to store the maximum of every length.

#include <iostream>
using namespace std;

const int maxn = 1e6;
int arr[maxn];

int main ()
{
    int n; cin>>n;
    for (int i=0;i<n;i++) { cin >> arr[i]; }

    int length = 2;
    int maxLength = 2; //max variable
    int cd = arr[1] - arr[0];
    for(int i=2; i<n; i++){
        if(arr[i] - arr[i-1] == cd) {length++;}
        else {
            cd = arr[i] - arr[i-1];
            length=2;
        }
        //cout<<length<<" "; //remove this
        maxLength = max(maxLength, length); //update maxLength
    }
    cout << maxLength;
}

A few more aesthetic notes:

array is a keyword in C++ used to declare std::array. Although the program may still run, it could create unnecessary confusion.
int array[n] is a VLAs (variable length array). It's not a C++ standard. It may or may not work depends on the compiler.
Why is "using namespace std;" considered bad practice?

@Sreekar If that's the case, can you mark the answer as correct? — silverfox, Nov 26 '21 at 15:39

C++ : Longest Arithmetic Subarray

2 Answers2