import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App()%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20random%0A%0A%20%20%20%20random.seed(47)%0A%20%20%20%20return%20(random%2C)%0A%0A%0A%40app.cell%0Adef%20_(random)%3A%0A%20%20%20%20nums%20%3D%20%5Brandom.randint(-100%2C%20100)%20for%20_%20in%20range(100)%5D%0A%20%20%20%20return%20(nums%2C)%0A%0A%0A%40app.function%0Adef%20kadane(nums)%3A%0A%20%20%20%20if%20not%20nums%3A%0A%20%20%20%20%20%20%20%20return%200%20%20%23%20Handling%20edge%20case%20for%20an%20empty%20list%0A%0A%20%20%20%20current_sum%20%3D%200%0A%20%20%20%20max_sum%20%3D%20nums%5B0%5D%20%20%23%20Start%20with%20the%20first%20element%0A%0A%20%20%20%20for%20num%20in%20nums%3A%0A%20%20%20%20%20%20%20%20%23%20Max%20of%20starting%20a%20new%20subarray%20or%20extending%20the%20current%20one%0A%20%20%20%20%20%20%20%20current_sum%20%3D%20max(num%2C%20current_sum%20%2B%20num)%0A%20%20%20%20%20%20%20%20max_sum%20%3D%20max(max_sum%2C%20current_sum)%20%20%23%20Update%20max_sum%0A%0A%20%20%20%20return%20max_sum%0A%0A%0A%40app.function%0Adef%20kadane_sliding_window(nums)%3A%0A%20%20%20%20if%20not%20nums%3A%20%20%23%20Handle%20edge%20case%20for%20empty%20input%0A%20%20%20%20%20%20%20%20return%200%2C%200%0A%0A%20%20%20%20max_sum%20%3D%20-float(%22inf%22)%0A%20%20%20%20cur_sum%20%3D%200%0A%20%20%20%20max_L%2C%20max_R%20%3D%200%2C%200%0A%20%20%20%20L%20%3D%200%0A%0A%20%20%20%20for%20R%2C%20num%20in%20enumerate(nums)%3A%0A%20%20%20%20%20%20%20%20%23%20Reset%20cur_sum%20and%20update%20L%20if%20cur_sum%20goes%20negative%0A%20%20%20%20%20%20%20%20if%20cur_sum%20%3C%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20cur_sum%20%3D%200%0A%20%20%20%20%20%20%20%20%20%20%20%20L%20%3D%20R%0A%0A%20%20%20%20%20%20%20%20%23%20Add%20the%20current%20number%20to%20cur_sum%0A%20%20%20%20%20%20%20%20cur_sum%20%2B%3D%20num%0A%0A%20%20%20%20%20%20%20%20%23%20Update%20max_sum%20and%20the%20indices%20if%20we%20find%20a%20new%20maximum%0A%20%20%20%20%20%20%20%20if%20cur_sum%20%3E%20max_sum%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20max_sum%20%3D%20cur_sum%0A%20%20%20%20%20%20%20%20%20%20%20%20max_L%20%3D%20L%0A%20%20%20%20%20%20%20%20%20%20%20%20max_R%20%3D%20R%0A%0A%20%20%20%20return%20max_L%2C%20max_R%0A%0A%0A%40app.cell%0Adef%20_(nums)%3A%0A%20%20%20%20max_subarray_sum%20%3D%20kadane(nums)%0A%20%20%20%20indices%20%3D%20kadane_sliding_window(nums)%0A%20%20%20%20assert%20sum(nums%5Bindices%5B0%5D%20%3A%20indices%5B1%5D%20%2B%201%5D)%20%3D%3D%20max_subarray_sum%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
791d74f3ae526db6f35bceec86c0621b