阿里笔试（3.20）第二题讨论= =

/*
dp法，时间复杂度O(n + 26*26), 空间复杂度O(26*26)。
记录sco[i]，代表此时末位为a~z每一种字母时，可以组成的最大长度
*/

//跳过不满足非递减字符串

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

bool illegal(string s1) {
    int i;
    for(i = 1; i < s1.length(); i++) {
        if(s1[i] - s1[i-1] < 0) {
            return 0;
        }
    }
    return 1;
}

void updateStrings(vector<vector<int> > &srecord, string s1) {
    if(illegal(s1)) {
        if(s1[0] == s1[s1.length()-1]) {
            srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] =
            srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] + int(s1.length());
        }
        else {
            srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'] =
            max(srecord[s1[0] - 'a'][s1[s1.length()-1] - 'a'], int(s1.length()));
        }
    }
    return;
}

//记录最大长度
int maxlen(vector<vector<int> > &srecord) {
    int start, end;
    int sco[26] = {0};
    
    for(end = 0; end < 26; end++) {
        for(start = 0; start <= end; start++) {
            sco[end] = max(sco[end], sco[start] + srecord[start][end]);
        }
    }
    return sco[25];
}


int main() {
    int n;
    cin>>n;
    int i;
    string s1;
    vector<vector<int> > srecord;
    vector<int> rtmp;
    
    for(i = 0; i < 26; i++) {
        rtmp.push_back(0);
    }
    for(i = 0; i < 26; i++) {
        srecord.push_back(rtmp);
    }

    for(i = 0; i < n; i++) {
        cin>>s1;
        updateStrings(srecord, s1);
    }
    
    cout<<maxlen(srecord)<<endl;
    
    return 0;
}

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

/*
dp法，时间复杂度O(n*26), 空间复杂度O(26)。
记录sco[i]，代表此时末位为a~z每一种字母时，可以组成的最大长度
*/

//跳过不满足非递减字符串
bool illegal(string s1) {
    int i;
    for(i = 1; i < s1.length(); i++) {
        if(s1[i] - s1[i-1] < 0) {
            return 0;
        }
    }
    return 1;
}


//记录最大长度
int maxlen(vector<string> &sing) {
    sort(sing.begin(), sing.end());
    int i, j;
    int sco[26] = {0};
    int start, end, maxv;
    for(i = 0; i < sing.size(); i++) {
        if(illegal(sing[i])) {
            start = sing[i][0] - 'a'; //当前单词首字母
            end = sing[i][sing[i].length()-1] - 'a';  //当前单词尾字母
            maxv = 0;
            for(j = 0; j <= start; j++) {
                maxv = max(maxv, sco[j]);  
                //能加入此单词的前面的尾字母有哪些，最长是多少
            }
            for(j = end; j < 26; j++) {
                sco[j] = max(sco[j], maxv + int(sing[i].length())); 
                //加入此单词的后，尾字母大于等于当前单词的长度都做更新
            }
        }
    }
    return sco[25];
}


int main() {
    int n;
    cin>>n;
    int i;
    vector<string> sing;
    string s1;
    
    for(i = 0; i < n; i++) {
        cin>>s1;
        sing.push_back(s1);
    }
    
    cout<<maxlen(sing)<<endl;
    
    return 0;
}