CODEWITHSUNDEEP
algorithmdiscrete-mathematics
user466796
user466796

Reputation: 315

What does this definition of contiguous subsequences mean?

I don't understand the following definition of a contiguous subsequence:

A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S.

If S is {5, 15, -30, 10, -5, 40, 10}
then 15, -30, 10 is a contiguous subsequence.

What makes 15, -30, 10 a contiguous subsequence?

Upvotes: 26

Views: 39425

Answers (11)

rohitt
rohitt

Reputation: 1235

Sequences are just ordered elements. S = a1, a2, a3 ..., an
for example, a sequence S could be: S = {5, 15, -30, 10, -5, 40, 10}
this can also be written as: S = 5, 15, -30, 10, -5, 40, 10

A subsequence of a sequence is where we pick some elements by preserving their relative order, and gaps are allowed in them.
Creating a subsequence is easy. Consider S = 1, 2, 3, 4, 5
now delete some elements, without changing the order of the remaining elements (see example).

for example: if S = 1, 2, 3, 4, 5
(we delete 2, 4)
then S' = 1, 3, 5 is a subsequence of S
and S'' = 1, 5, 3 is not a subsequence of S because the order of 5 and 3 is not preserved

Contiguous subsequences are subsequences that do not have gaps in them. they are somewhat equivalent to subarrays.
Formally, S' is a subsequence of S if S' = ai, ai+1, ai+2 ..., aj-1, aj where 1 <= i <= j <= n, and i and j are both positive integers.

For example: if S = 1, 2, 3, 4, 5, 6, 7
then S' = 4, 5, 6 is a contiguous subsequence.
and S'' = 2, 4, 5, 6 although is a subsequence of S, but is not a contiguous subsequence of S.

(Do not confuse subsequences with sets. This could be because we sometimes use set notations for them (like {}). Sequences have ordered elements. Just some addition to information is that all contiguous subsequences are still subsequences, but not all subsequences are contiguous subsequences.)

Now, the answer to OPs question becomes obvious.
15, -30, 10 is a contiguous subsequence because it is both a subsequence (the subsequence maintains the original relative order of elements) and its elements are contiguous (Here, a2 = 15, a3 = -30, and a4 = 10. The indices/positions are continuous natural numbers). Thus it is a contiguous subsequence.

Upvotes: 2

Paul Pavlish
Paul Pavlish

Reputation: 1

15, -30, 10 is not a contiguous sequence.

The answer from user brad would indicate that the sequence of numbers you referenced is not contiguous. You can also validate this by running code from geeksforgeeks.org.

Upvotes: -2

Abhishek Kaushik
Abhishek Kaushik

Reputation: 1169

Lets say you have some elements in a subsequence,

then it will be called contiguous iff the elements taken in order are consecutive in original set.

E.g,

Sequence=2,3,abc,5.6,4,abhishek;

Subsequence=5.6,2,abhishek;

Contiguous Subsequence=3,abc,5.6 or 5.6,4,abhishek or abc,5.6.

Remember, The sequence itself is always a contiguous subsequence.

Hope it makes the concept clear!

Upvotes: 15

sarfarazsajjad
sarfarazsajjad

Reputation: 1238

In the series (5,15,-30,10,-5,40,10) 5,15,-30 are one after another so they are contiguous but 5,15,40 are not contiguous because we skipped -30,10, and -5 and took 40. In Dasgupta's book, we need to find a sub series of the main series which makes the largest possible sum. Which in this case is 10,-5,40,10. Which is (10-5+40+10=55).

Upvotes: 4

FeralWhippet
FeralWhippet

Reputation: 43

A subsequence can be formed from any subset of items from the original subsequence, so from above {5,10,40} is a valid subsequence. A contiguous subsequence is more restricted, it requires the elements to be consecutive elements from the list, NOT that the values are consecutive but that the positions of the elements taken from the original are consecutive. I suspect that this distinction was the OPs point of confusion.

Upvotes: -1

Md ALam
Md ALam

Reputation: 11

Respectively list some elements from array S without skipping any element from the middle of that list.

Upvotes: 1

Brad
Brad

Reputation: 15577

The form a subset that are next to each other within the set.

con·tig·u·ous/kənˈtigyo͞oəs/Adjective
1. Sharing a common border; touching.
2. Next or together in sequence.

Upvotes: 9

user191776
user191776

Reputation:

Contiguous elements are consecutive elements.

Upvotes: 2

user483085
user483085

Reputation: 71

They are elements of your original array and they are all continous.

Upvotes: 2

Jack
Jack

Reputation: 133659

This is not directly programming related but 15, 30, -15 is a contiguous subsequence because you can find them in the same order inside the given list (without any holes between the elements of course).

Upvotes: 4

Albin Sunnanbo
Albin Sunnanbo

Reputation: 47068

Uhm, maybe because they are consecutive as per your definition?

Upvotes: 2

Related Questions