how we can apply in the question ???

11 votes

Consider a sequence of $14$ elements: $A=[-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]$. The sequence sum $S(i,j) = \Sigma_{k=i}^j A[k]$. Determine the maximum of $S(i,j)$, where $0 \leq i \leq j <14$. (Divide and conquer approach may be used.)

Answer: ___________

Answer: ___________

19 votes

Best answer

Subsequence : A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Subarray : A subarray of n-element array is an array composed from a contiguous block of the original array's elements.

Question is asking for subsequence.

$S(i,j) = \sum_{k=i}^j A[k]$

What does $\sum_{k=i}^j $ mean? It means you start from index $i$ and go till index $j$ with unit increment each time.

Ultimately they are asking 'Maximum subarray sum'.

int maxsum = A[0], sum = A[0], n=14; for(int i=1; i<n; i++){ if (A[i]>A[i-1) { if (sum > 0) sum+=A[i]; else sum = A[i]; } else sum = A[i]; if (maxsum < sum) maxsum = sum; }

sum $=6 + 3 - 1 - 2 + 13 + 4 - 9 - 1 + 4 + 12 = 29$

2

It's just to know the answer. Divide and Conquer doesn't need here this case because noticing the array watchfully, we can find maximum subarray sum. See **Kadane’s Algorithm**.

12 votes

29 for the the subsequence (6, 3, -1, -2, 13, 4, -9, -1, 4, 12)

Use kadanes algorithm or mental brute force is good to go with !!!

Use kadanes algorithm or mental brute force is good to go with !!!

0

if there are n elements in the list then

$2^{n}.$ will be.

Here talking about subsequence sub not subarray sum ??

then should be 42 ??

$2^{n}.$ will be.

Here talking about subsequence sub not subarray sum ??

then should be 42 ??

0

They have defined the definition of subsequence in question explicitly. So it should be clear from that.

0

There is noting the word contiguous in the question ???

42 should be the answer because they are talking about subsequence.

1

Divide & conquer

Greedy

Dynamic Programming

all these are algorithm design paradigms, you can use these paradigms while solving your problem !

ex:- problem is sorting but paradigm may be Divide & conquer or Greedy or Dynamic.

For this question :- problem is " Finding maximum sub array sum ", paradigm may be use Divide & conquer.

https://www.geeksforgeeks.org/maximum-subarray-sum-using-divide-and-conquer-algorithm/

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

3 votes

Taking 6 to 12 the largest sum will be 29.

While trying to take positives, negatives also need to be taken so sum shrinks to 29.

While trying to take positives, negatives also need to be taken so sum shrinks to 29.

1 vote

Logic: as pattern can be seen, it's consecutive positives and consecutive nevatiy.

So 1st two and last two are to be ignored for sure.

Combine remaining as pairs of two as if 1 positive counted then next also, if one negative ignored other shall also be.

This way I made pairs out of it as below:

-15, 9, -3, 17,-12,16,-3.

Now check all three middle combination.

I got 29

So 1st two and last two are to be ignored for sure.

Combine remaining as pairs of two as if 1 positive counted then next also, if one negative ignored other shall also be.

This way I made pairs out of it as below:

-15, 9, -3, 17,-12,16,-3.

Now check all three middle combination.

I got 29

1 vote

Just by observation, the subsequence with the maximum sum would be from 6 to 12.

So, $6+3−1−2+13+4−9−1+4+12$

=> $29$.

So, $6+3−1−2+13+4−9−1+4+12$

=> $29$.

0 votes

There is a basic DP problem, which can be formulated as follow:

Let $S[i]$ be the maximum sum till the $ith$ index.

The answer we are looking for is $S[n]$ i.e the maximum sum that is possible till the last index.

Now, the recursion for the DP can be written as follows:

$S[i] = max(S[i-1] + a_i, S[i-1])$

The first term refers to the fact when the element we add is positive and adds to the sum, the second term is used when the current term doesn't do us any favour.

Using this, the answer can be easily found out to be 29.

Let $S[i]$ be the maximum sum till the $ith$ index.

The answer we are looking for is $S[n]$ i.e the maximum sum that is possible till the last index.

Now, the recursion for the DP can be written as follows:

$S[i] = max(S[i-1] + a_i, S[i-1])$

The first term refers to the fact when the element we add is positive and adds to the sum, the second term is used when the current term doesn't do us any favour.

Using this, the answer can be easily found out to be 29.