# DP and sort C++ 69ms beats 99%

• Since for each city it need to search N flights, so for each week it will be NN
a little improvement is to sort next week's information, which is N
logN and then to search the max value. However in worst case, it will still cost N*N

int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
int cities=days.size(),weeks=cities==0?0:days[0].size();
if(cities==0 || weeks==0)return 0;
for(int i=weeks-2;i>=0;i--)
{
vector<pair<int,int>> rank;
for(int j=0;j<cities;j++)rank.push_back({days[j][i+1],j});
sort(rank.begin(),rank.end(),[](pair<int,int> x,pair<int,int> y){return x.first>y.first;});
for(int j=0;j<cities;j++)
{
int k=0;
while(k<cities && (!flights[j][rank[k].second] && rank[k].second!=j ))k++;
if(k<cities)
days[j][i]+=rank[k].first;

}
}

int result=days[0][0];
for(int i=1;i<cities;i++)if(flights[0][i])result=max(result,days[i][0]);
return result;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.