Maximum Score of Valid Parentheses Substring Length

amazon Given a string consisting only of '(' and ')', find its maximum score. The score is defined as: for two indices i and j, if the substring s[i:j+1] is a valid set of parentheses, the score is j - i. Return the maximum score possible. The input string has a length of up to 1000. Example Input ()