Subarray
A subarray is a contiguous portion of an array taken from a starting index i to an ending index j, where 0 <= i <= j and the elements included are a[i], a[i+1], ..., a[j]. The length of this subarray is j - i + 1. Subarrays are defined with respect to the original array and preserve the order of elements.
For example, in the array [5, 7, -2, 3, 9], the subarray from index 1 to 3
Difference from subsequence: A subarray must be contiguous, meaning no elements are skipped between the endpoints.
Applications and properties: Subarrays are central to many algorithmic problems, such as finding the maximum subarray
Computation: Subarray sums can be computed efficiently with prefix sums, enabling O(1) queries for any i..j after
Terminology: In strings, a similar concept is called a substring; the idea is parallel to a 1D