The sliding window algorithm is an efficient tool for providing solutions to problems involving the selection and comparison of subsets within arrays and strings. Examples of such problems include finding the maximum sum subarray of a given size, fin...
Markdown supported · ⌘↵ to post
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
yetanothertroll
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