求最长有效括号长度 求出一串由：‘(’和‘)’组成的字符串中最长有效括号的长度。例如：(()()，结果是4。((()))结果是6。())()()结果是4。 输入提示："Please input the array\n" 输入格式：%s 输出格式："The longest length is %d\n" 程序输入输出示例 Please input the array ()()() The longest length is 6 函数原型为 int longestValidParentheses(char* s)

以下是使用栈的方法实现：

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

#define MAX_N 100000

int longestValidParentheses(char* s) {
    int n = strlen(s);
    int* stk = (int*)malloc(sizeof(int)*n);
    int top = -1;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '(') {
            stk[++top] = i;
        } else {
            if (top == -1) {
                continue;
            }
            int len = i - stk[top--] + 1;
            if (top == -1) {
                len = i + 1;
            } else {
                len = i - stk[top];
            }
            ans = ans > len ? ans : len;
        }
    }
    free(stk);
    return ans;
}

int main() {
    char s[MAX_N];
    printf("Please input the array\n");
    scanf("%s", s);
    printf("The longest length is %d\n", longestValidParentheses(s));
    return 0;
}

使用动态规划的方法实现：

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

#define MAX_N 100000

int longestValidParentheses(char* s) {
    int n = strlen(s);
    int* dp = (int*)malloc(sizeof(int)*n);
    memset(dp, 0, sizeof(int)*n);
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        if (s[i] == ')') {
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
            }
        }
        ans = ans > dp[i] ? ans : dp[i];
    }
    free(dp);
    return ans;
}

int main() {
    char s[MAX_N];
    printf("Please input the array\n");
    scanf("%s", s);
    printf("The longest length is %d\n", longestValidParentheses(s));
    return 0;
}