Sliding Window Algorithm

The maximum subarray sum with one deletion does not appear to be faster than O(n²) even using sliding window. I can almost but not quite grasp a "dynamic programming" approach to speed it up aargh

Wow, code in comments gets mangled and trying to edit comments fails

Why not use BASIC? Admittedly adding a good data structure for tracking duplicated elements within the window, dropping a negative element, and maybe max sum of sums might be 'interesting' in BASIC lol

Written in X11 BASIC for Android ver. 1.28-65 18/8/2022 build

Not the tightest code ever, but we all learn the hard way to optimize for readability when a bug is found a year later don't we

Program Sliders

! Can Nums() include negative numbers?

Nums() = [ 2, 1, 5, 1, 3, 2 ]

k% = 3

Clr c_l%, c_r%, c_sum

Clr max_l%, max_r%, max_sum

Print k%, Dim?(Nums())

! max_sum = -1e200

For c_r% = 0 To Dim?(Nums()) - 1

If k% < (c_r% - c_l% + 1) ! Beware of fencepost error

Sub c_sum, Nums(c_l%)

Inc c_l%

EndIf

Add c_sum, Nums(c_r%)

! Invariants: (Hopefully lol)

! Count of Nums(c_l% : c_r%) <= k%

! Sum of Nums(c_l% : c_r%) = c_sum

Print "Check", c_l%, c_r%, c_sum

If (k% = (c_r% - c_l% + 1)) And (c_sum > max_sum)

max_l% = c_l%

max_r% = c_r%

max_sum = c_sum

Print "New max", max_l%, max_r%, max_sum

EndIf

Next c_r%

Print "Result", max_l%, max_r%, max_sum

Print "OK"

End