OT:

Cumulative sums are fun. Here's its application (sum "-1" and "1"s, but with "saturation": don't fall below zero) for another task, PWC 346-1 "Longest Parenthesis". There are at least half a dozen identical (i.e. verbatim) Perl solutions, doesn't matter if it's because task is trivial, or "AI" was involved, or subroutine was copied. In fact, that Perl solution is significantly faster for medium and long inputs than a few others based on nested loops or regular expressions. Below is my translation of it to C. (I'm not fluent in C, can it be written better? Hopefully, I haven't put it in much disadvantage because of that.)

Surprisingly, my "cumulative sum" solution is faster, though it involves second sweep over input and seemingly more arithmetic. For shorter, 1000 random strings 1000 chars long:

v5.42.0 / MSWin32-x64-multi-thread / 13.2.0
     Rate  pwc  sum
pwc 199/s   -- -46%
sum 365/s  84%   --
[download]

And for set of 100 of longer strings (100_000 length):

      Rate  pwc  sum
pwc 21.4/s   -- -56%
sum 48.2/s 125%   --
[download]

Why C and, hence, OT? I had Perl prototype, somewhat faster than mentioned Perl PWC solution; then did PDL prototype (~ 10x .. 20x faster, of course), but had to write a small PP fragment for it; and thought why not do it in C completely then, anyway. Had no intention to translate PWC Perl to C for competition; but found C++ solution in GH PWC directory. Something to compile to machine code, hurray. Well, for a single 1e6 chars long string it took twenty seconds, no joking. (C functions, below, are in milliseconds).

Perl code for the results above:

use strict;
use warnings;
use feature 'say';
use Config;
use Benchmark 'cmpthese';

say "$^V / $Config{ archname } / $Config{ gccversion }";

my $L = 1e5;
my $s = '(' x $L;
my @samples;

for ( 0 ... 99 ) {
    my $s1 = $s;
    for ( 0 .. $L - 1 ) {
        substr $s1, $_, 1, ')' if int rand 2
    }
    push @samples, $s1;
    die unless longest_p_pwc( $s1 ) ==
               longest_p_sum( $s1 )
}

cmpthese -3, {
    pwc => sub { longest_p_pwc( $_ ) for @samples },
    sum => sub { longest_p_sum( $_ ) for @samples },
};

sub valid_longest_parenthesis {
    my $s       = shift;
    my @stack   = (-1);
    my $max_len = 0;

    for my $i (0 .. length($s) - 1) {
        if (substr($s, $i, 1) eq "(") {
            push @stack, $i;
        } else {
            pop @stack;
            if (@stack) {
                $max_len = $max_len > ($i - $stack[-1])
                          ? $max_len : ($i - $stack[-1]);
            } else {
                push @stack, $i;  # New starting point
            }
        }
    }

    return $max_len;
}

use Inline C => << 'END_OF_C';

int longest_p_pwc( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
    
    int* stack = malloc( len * sizeof( int ));
    int stack_i = 0;
    stack[ 0 ] = -1;

    int max = 0;
    for ( int i = 0; i < len; i ++ ) {
        if ( buf[ i ] == '(' ) stack[ ++ stack_i ] = i;
        else {
            if ( stack_i > 0 ) {
                stack_i --;
                int cur = i - stack[ stack_i ];
                if ( cur > max ) max = cur;
            }
            else stack[ 0 ] = i;
        }
    }
    free( stack );
    
    return max;
}

int longest_p_sum( SV* str ) {
    STRLEN len;
    char* buf = SvPVbyte( str, len );
   
    int* pad = malloc( len * sizeof( int ));
    int sum = 0;
    for ( int i = 0; i < len; i ++ ) 
        pad[ i ] = sum = 
            sum + !sum + ( buf[ i ] == '(' ? 1 : -1 );
    int max = 0;
    int cur = 0;
    int counting = 0;
    int zeroless = 1;
    sum = 0;
    for ( int i = len - 1; i >= 0; i -- ) {
        zeroless = zeroless && pad[ i ];
        sum = zeroless 
            ? sum + !sum + ( buf[ i ] == ')' ? 1 : -1 ) 
            : 1;
        if ( pad[ i ] && sum ) {
            cur ++;
            counting = 1;
        }
        else if ( counting ) {
            if ( cur > max ) max = cur;
            counting = 0;
            cur = 0;
        }
    }
    if ( cur > max ) max = cur;
    free( pad );
    
    return max;
}

END_OF_C
[download]