Definition of subarray

I am unclear about the definition of a sub array. Does it mean a contiguous list of inde开发者_开发百科xes , such as a[i..j] or can it be non contiguous, such as a[0], a[5],a[6]

Subarrays are arrays within another array.Subarrays contains contiguous elements whereas subsequences are not.

An Example would make it clear

Consider an array {1,2,3,4}

List of all its subarrays are {},{1},{2},{3},{4},{1,2},{2,3},{3,4},{1,2,3,4}

List of all its subsequences are {},{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}

I think the subarray means the array in which the contiguousness is based on the index . for example lets take an example

2 3 1 3 1 (index are 0,1,2,3,4 respectively )

so subarray is 2,3,1 3 (index 0,1,2,3) But (1,2 1) (index 2,0,4) cannot be a subarray coz the indexes are non-contiguous ..

Hope its helpfull ;)

In most contexts it refers to a contiguous index subset.

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Subarray refers to contiguous list whereas Subsequence refers to non-contiguous list.

Well, SubArray is contiguous and SubSequence is not. if you want to full note click on the link mentioned in the end. if you are too lazy to click then read here :


Here is the Definition of Subarray and SubSequeences: A subbarray is a contiguous part of array. An array that is inside another array. For example, consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays. The subbarays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4). In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/subsrings.

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements. For the same example, there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). More generally, we can say that for a sequence of size n, we can have (2^n-1) non-empty sub-sequences in total. and including empty subsequence 2^n subsequences in total

Definition / Credit : Click Here to Read full note / SubArry And SubSequence