Search for a command to run...
Professional software engineer working at CoverMyMeds, an enterprise healthtech firm that ensures patients get access to the medication they need.
Primarily focused on backend and systems design through Ruby and Elixir, but experienced with JavaScript and all things frontend
Interested in learning and teaching the craft of software; technical or otherwise
Join me as I innovate by iterating!
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
Austin My stabs at the leetcode problems can be found here https://forums.craigslist.org/?forumID=9510
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
The state of software and the internet is insane. Most websites are unfindable. Every Google search is dominated by SEO marketers. The internet has lost its beauty in the fiasco of widespread adoption and has been immensely over-capitalized. Apps can...
My origin story
Ever feel like you're juggling too many tasks, and constantly dropping the ball? I've been there. Let me share these secret weapons I wish I'd had in my arsenal sooner. Over the past few months, I've had a lot of different work to do. Juggling my job...
Today we're gonna take a stab at a Medium LeetCode problem. For a long time I never even attempted these because I was worried that they'd be "too hard", but this example will demonstrate that this is not the case. Join me as we dive into the problem...
If you're struggling with LeetCode problems, algorithms and data structures, or job interview prep, hash maps are a great tool to have in your tool belt. They're fast, flexible, and easy to implement. Other languages like Ruby utilize hashes specific...
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, finding the length of the longest substring without repeating characters, and finding the minimum window substring containing all characters of a given string. After understanding how the window sliding algorithm works, one could feasibly complete this Medium LeetCode problem: https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/
In this post, we will be tackling a simpler modification of the above problem. We'll detail how you can find the maximum sum subarray of a given array, with a subarray size of K.
Problem statement:
Given an array of integers and an integer k, find the maximum sum of any contiguous subarray of size k.
Input:
An array nums containing n integers, where 1 <= n <= 10^5
An integer k, where 1 <= k <= n
Output:
kInput: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
And a potential solution in ruby:
def max_sum_subarray(nums, k)
max_sum = 0
window_sum = 0
window_start = 0
nums.each_with_index do |num, window_end|
window_sum += num # Add the next element to the window sum
if window_end >= k - 1 # If the window size is >= k
max_sum = [max_sum, window_sum].max # Update the max_sum if needed
window_sum -= nums[window_start] # Remove the element going out of the window
window_start += 1 # Slide the window
end
end
max_sum
end
nums = [2, 1, 5, 1, 3, 2]
k = 3
puts max_sum_subarray(nums, k) # Output: 9
In this implementation, we initialize a window_sum. This represents the sum of elements within the sliding window.
We iterate through the array, adding elements to the window_sum.
When the window size is greater than or equal to k, we update the max_sum and remove the element that is no longer in the window.
I've included a diagram below, to help demonstrate how this works:
Hopefully, the sliding window algorithm is a bit clearer now. Like most, these problems start simple but then require additional considerations as the problems get more complicated.
If you're interested in advancing your algorithm skills with the sliding window, here are two Medium LeetCode problems that can be solved using a similar technique:
https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/
https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/
Thanks for reading!