【面接筆記試験アルゴリズム】Problem 9:テンセント2016年研究開発実習筆記試験問題:最長回文子串

(一)テーマ
質問:与えられた文字列sの返信(palindrome)サブ列の中で、最も長い返信サブ列の長さを求めます.返信(palindrome)は左から右へ読む文字列と右から左へ文字列を読む文字列で、見える文字列は同じです.例えば「cabbeaf」、回文のサブストリングは「c」「aba」「abba」などを含み、最も長いサブストリングは「abba」であり、長さは4である.プログラム入力:「cabbeaf」プログラム出力:4
(二)問題を解く
当時筆記試験の時はACがなく、オフラインはVSで引き上げられた.この方法の主な考え方は、動的計画で、1つのpath[i][j]配列を利用して文字列iからjまでの最長回文長を記録し、状態遷移方程式は以下の2つの状況に分けられる:1、s[i]==s[j]の場合、回文列長はpath(i+1、j-1)+2;2、s[i]!=s[j]の場合、max(path(i+1、j)、path(i、j-1);

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

int path[1000][1000] ={0}; 
int maxlen=0;
int findPalindrome(string& s,int start , int end)
{
    if (start > end) 
        return 0;
    if (start == end) 
        return 1;
    if (path[start][end] != 0) 
        return path[start][end];
    if (s[start] == s[end])
    {
        path[start][end] = findPalindrome(s,start+1,end-1) +2;
        if (maxlen<path[start][end])
        {
            maxlen = path[start][end];
        }
    }
    if (s[start] != s[end])
    {
        int temp1 =findPalindrome(s,start+1,end);
        int temp2 =findPalindrome(s,start,end-1);
        path[start][end] = temp1>temp2?temp1:temp2;
        if (maxlen<path[start][end])
        {
            maxlen = path[start][end];
        }
    }
    return maxlen;
}
int main (){
    string s = "cabbeaf";
    findPalindrome(s,0 ,s.length()-1);
    cout<<maxlen<<endl;
    return 0;
}

OJプラットフォームでテストしていないし、ACができるかどうか分からないし、どうせ大体そうだと思います.