Central idea is to be able to extend valid parentheses, like `()()`

notice that the second `()`

extends the previous valid parenthesis to give a length of 4.

Other examples:

`()(()`

- in this case, longest valid is 2, but the moment we add another parentheses at the end `()(())`

, the whole string becomes a valid parentheses, so it is important to remember at `i = 2`

that there was a valid parentheses that ended just before it, so if a valid parentheses is created using `i=2`

as the starting point (opening parenthesis), the previous length can be added to it.

For this, we can use an array (I call this array `LengthEndingAtIndex`

as it stores the length of valid parenthesis ending at every offset. Whenever I find a valid parentheses (using a stack), I just store the current valid length into this array.

Please let me know if any part is not clear, beginner here.

```
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
maxLen = 0
currentRun = 0
LengthEndingAtIndex = [0 for i in range(0, len(s)+1)]
for i in range(0, len(s)):
if len(stack) == 0:
if s[i] == '(':
stack.append((i, s[i]))
continue
topOfStackIndex, topOfStackParenthesis = stack[-1]
if s[i] == ')':
if topOfStackParenthesis == '(':
stack = stack[0:-1]
currentRun = (i - topOfStackIndex + 1) + LengthEndingAtIndex[topOfStackIndex]
maxLen = max(currentRun, maxLen)
LengthEndingAtIndex[i+1] = currentRun
continue
else:
stack.append((i, s[i]))
return max(LengthEndingAtIndex)
```