subarrays

Subarrays are contiguous segments of an array. A subarray is determined by two indices i and j with 0 ≤ i ≤ j < n, and consists of the elements a[i], a[i+1], ..., a[j]. The length is j − i + 1. Subarrays must be contiguous; a subsequence may skip elements.

For an array of length n, the number of non-empty subarrays is n(n+1)/2. For example, in [1, 2, 3, 4], the subarrays include [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4].

Subarrays are a fundamental concept in array algorithms. They are defined by start and end indices and can be used to express properties such as sums, products, or other aggregations over contiguous blocks. They are distinct from subsequences, which may skip elements.

Common problems include finding the maximum subarray sum, counting subarrays that meet a sum constraint, or finding a subarray with a given length or sum. Efficient solutions often rely on prefix sums, which allow O(1) subarray sum queries after O(n) preprocessing, and on sliding-window or two-pointer techniques for constraints tied to the subarray endpoints. Kadane's algorithm computes the maximum subarray sum in linear time.

In 2D, the analogue are submatrices of a matrix. In strings, a string can be treated as an array of characters, so character subarrays (also called substrings) are a common special case. Subarray concepts provide a building block for many algorithms and data-analysis tasks.