3.9k views
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.)

edited | 3.9k views

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$

by Veteran (60.9k points)
selected
0
Divide and Conquer may be used ??

how we can apply in the question ???
0
0

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.

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 !!!
by Active (2.7k points)
0
What is the difference between subsequence and subarray?
0

What is the difference between subsequence and subarray ???

0

@ sir @ sir Can't we sort the array (using D & C) & then sum all +ve integer to get maximum value??

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  ??
0
They have defined the definition of subsequence in question explicitly. So it should be clear from that.
0
can't we use merge sort & then perform subsequence sum a/c to given question?
0

I'm not getting you sir. Please explain.

0

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

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

0
I too got 42
0

@kumar.dilip

what is the definition of s(i,j) in the question ?

0
we can sort the given list ???
+1

@kumar.dilip

u have to find the maximum in a continuous run, u cant skip some of the values in the middle

0

what's meaning of divide and conquer there ??

0
It is one of the algorithms paradigms..
0

what's wrong here?? By using D & C :-

0

@Naveen Kumar 3

Did you mean, " Divide and conquer = Sorting " ?

0

I thought the same. What does it mean @Shaik sir?

+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/

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.
by Active (1.1k points)
+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$.
by Loyal (6.6k points)
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
by Junior (675 points)
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.
by Loyal (6.7k points)