괄호와 일치하는 최장 하위 열의 길이를 구합니다(Longest Valid Parentheses).

제목 설명:
Given a string containing just the characters’(’ and’)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is”()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.
번역:
'(' 와 ')' 을 포함하는 문자열을 정하고 가장 긴 유효한 괄호와 서브열의 길이를 찾아라.
해법 1:
이 문제는 1차원 동태 기획으로 역방향으로 해답을 구할 수 있다.괄호 표현식이 Strings라고 가정하고 s.length 길이의 1차원 그룹 dp[]를 유지하고 그룹 요소를 0으로 초기화합니다.dp[i]는 s[0]에서 s[i]까지 s[i]를 포함하는 가장 긴 유효한 일치 괄호 문자열의 길이를 나타낸다.다음과 같은 관계가 존재한다.dp[0] = 0; 2.i는 1->strlen(s)-1에서 dp[i]를 구하고 최대치를 기록한다.만약 s[i]=')'가 있다면 s에서 i부터 0까지 dp[i]의 값을 계산합니다.이 계산은 두 단계로 나뉘는데 dp[i-1]을 통해 진행되었다(dp[i-1]가 이미 이전 단계에서 해를 구했음을 주의한다): (1).s에서 i-1의 끝에서 유효한 괄호와 일치하는 자열의 길이, 즉 dp[i-1]를 찾고 이 유효한 괄호 자열을 건너뛰고 앞의 문자를 보십시오. 그 다음은 j=i-1-dp[i-1]입니다.만약 j가 경계를 넘지 않고 s[j]='(), s[i...j]는 유효한 괄호와 일치하며 dp[i]=dp[i-1]+2.(2).s[i...j]의 유효한 일치 길이를 구한 후에 j-1이 경계를 넘지 않으면 dp[i]의 값은 j-1의 끝에서 가장 긴 유효한 일치, 즉 dp[i]+=dp[j-1]를 더해야 한다.
해법 2:
이 문제는 1차원 동태 기획으로 역방향으로 해답을 구할 수 있다.괄호 표현식이 Strings라고 가정하고 s.length 길이의 1차원 그룹 dp[]를 유지하고 그룹 요소를 0으로 초기화합니다.dp[i]는 s[i]에서 s[s.length-1]까지 s[i]를 포함하는 가장 긴 유효한 일치 괄호 문자열의 길이를 나타낸다.다음과 같은 관계가 존재한다.dp[s.length - 1] = 0; 2.i는strlen(s)-2->0에서 dp[i]를 역방향으로 구하고 최대치를 기록한다.만약 s[i]='('라면 s에서 i부터 s.length-1까지 dp[i]의 값을 계산합니다. 이 계산은 두 단계로 나뉘어 dp[i+1]을 통해 진행됩니다. (dp[i+1]은 이미 이전 단계에서 구해가 있음을 주의하십시오): @ s에서 i+1에서 i+1부터 유효한 괄호의 일치하는 자열 길이, 즉 dp[i+1]를 찾아 이 유효한 괄호 자열을 건너뛰고 다음 문자를 보십시오. 그 다음은 j=i+1+[dpi+1]입니다.만약 j가 경계를 넘지 않고 s[j]=')'가 없다면 s[i...j]는 유효한 괄호와 일치하고 dp[i]=dp[i+1]+2이다.s[i...j]의 유효한 일치 길이를 구한 후에 j+1이 경계를 넘지 않으면 dp[i]의 값에 j+1에서 시작하는 가장 긴 유효한 일치, 즉 dp[j+1]를 추가합니다.

#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

char s[maxn];
int dp[maxn];

int solve1(int len, char s[]) {
    int Max = 0;
    for(int i = 0; i < len; i++)
        dp[i] = 0;
    for(int i = 1; i < len; i++) {
        if(s[i] == ')') {
            int j = i-1-dp[i-1];
            if(j >= 0 && s[j] == '(') {
                dp[i] = dp[i-1] + 2;
                if(j-1 >= 0) 
                    dp[i] += dp[j-1];
            }
        }
        if(Max < dp[i]) Max = dp[i];
    }
    return Max;
}

int solve2(int len, char s[]) {
    int Max = 0;
    for(int i = 0; i < len; i++) 
        dp[i] = 0;
    for(int i = len-2; i >= 0; i--) {
        if(s[i] == '(') {
            int j = i + 1 + dp[i+1];
            if(j < len && s[j] == ')') {
                dp[i] += dp[i+1] + 2;
                if(j+1 < len)
                    dp[i] += dp[j+1];
            }
            if(Max < dp[i]) Max = dp[i];

        }
    }
    return Max;
}

int main(){
    while(~scanf("%s", s)){
        int len = strlen(s);
        printf("%d
", solve1(len, s));
        printf("%d
", solve2(len, s));
    }
    return 0;
}