#include <iostream>
#include <unordered_map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
int longestAPLength(vector<int> arr)
{
int n=arr.size();
unordered_map<int,set<int>> mp;
for(int i=0;i<n;i++)
{
mp[arr[i]].insert(i);
}
int count=2,ans=2;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
int diff=arr[j]-arr[i];
int num=arr[j]+diff;
count=2;
if(mp.find(num)!=mp.end())
{
while(mp.find(num)!=mp.end())
{
auto it=mp.find(num);
set<int> vc=it->second;
int pos=-1;
for(auto it2=vc.begin();it2!=vc.end();++it2)
{
if(*it2>j)
{
pos=*it2;
break;
}
}
if(pos!=-1){
count++;
num=num+diff;
}
else
{
break;
}
}
}
ans=max(ans,count);
}
}
return ans;
}
int main() {
string s;
getline(cin,s);
vector<int> vc;
int dig=0;
for(int i=1;i<s.length();i++)
{
if(s[i]!=',' && s[i]!=']')
{
dig=(s[i]-'0')+dig*10;
}
else{
vc.push_back(dig);
dig=0;
}
}
cout<<longestAPLength(vc);
return 0;
}Getting TLE for test case2 and test case 3,while rest 2 test cases pass
Your code complexity is O(n^3).Reduce it to O(n^2).
For that store a vector of map which gives size of ap for a given difference till ith index.
Now,for every index,iterate for all previous index and calculate the difference between current index and that index do:
v[i][x]=v[j][x]+1 where i is current index and j is previous index that we are iterating and x is diffrence between the two elements,v is vector of map.
For code see the link: