7
$\begingroup$

What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what contiguous in this actually is.

Ex: Wikipedia: Maximm subarray problem has no explanation of why the given "subarray" is contiguous or what contiguous means in the context.

$\endgroup$
2
  • 1
    $\begingroup$ I believe it's just a contiguous (in order) subset of the set. The Wikipedia page you referenced, in the first paragraph gives an example: "For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6." $\endgroup$ – Jared Jun 6 '15 at 4:52
  • $\begingroup$ Nicely explained with program: javabypatel.blogspot.in/2015/08/… $\endgroup$ – Jayesh Oct 23 '15 at 11:25
7
$\begingroup$

This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an interval of the indices: a first and last element and everything between them.

$\endgroup$
1
  • $\begingroup$ This answer is misleading in the sense that a subarray, in most articles/books/videos/programming languages/situations, means a contiguous slice of the original array. Sometimes people write contiguous subarray for the sake of extra clarity, which is a bad practice. If one want to be clearer, write contiguous subsequence instead. All respectable definitions of a subarray that I can remember require the indices selected be contiguous. On the other hand, a subsequence is (overwhelmingly if not always) defined without that requirement. $\endgroup$ – John L. Feb 17 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.