Subarray

Refer the problem statement: Maximum Subarray Sum Let us try to understand how Kadane’s Algorithm work. This solution is similar to sliding window in a way. Pseudocode For at-least 1 non-negative numbers Here’s the pseudocode for Kadane’s algorithm based on your template, designed to handle arrays with non-negative sums: # Start maxGlobal <- 0 maxCurrent <- 0 # Loop over array for i from 0 to n-1 do maxCurrent <- maxCurrent + a[i] # If maxCurrent drops below 0, reset it to 0 if maxCurrent < 0 then maxCurrent <- 0 end if # Update maxGlobal if we've found a new maximum if maxGlobal < maxCurrent then maxGlobal <- maxCurrent end if end for ...

Definitions A subarray is a contiguous part of array and maintains relative ordering of elements. For an array/string of size n, there are n*(n+1)/2 non-empty subarrays/substrings. A subsequence maintain relative ordering of elements but may or may not be a contiguous part of an array. For a sequence of size n, we can have 2^n-1 non-empty sub-sequences in total. A subset MAY NOT maintain relative ordering of elements and can or cannot be a contiguous part of an array. For a set of size n, we can have (2^n) sub-sets in total. ...

Problem Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead. OR Given an array of positive integers a and a positive number K, find the length of the smallest contiguous subarray whose sum is greater than or equal to K. Return 0 if no such subarray exists. ...