retagged by
19,050 views
23 votes
23 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: ___________
retagged by

9 Answers

1 votes
1 votes
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
0 votes
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.
0 votes
0 votes
int Sub_array_sum[ ], a[ ], i, n, m, sum=0;
      for(i=0; i<n: i++)
      {
              sum = sum + a[i];
              if(sum<0)
                             Sub_array_sum[ ] = sum;
              else
                               sum = 0;
          }
        

          int max_sub_array_sum = Sub_array_sum[0];
          for(i=1; i<m; i++)
           {
                  if(max_sub_array_sum < Sub_array_sum[i])
                            max_sub_array_sum = Sub_array_sum[i];
             }
             Return  max_sub_array_sum;

for the given problem A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]
we, get
               Sub_array_sum[ ] ={ 6, 9, 8, 6, 19, 23, 14, 13, 17, 29, 26, 26 }
and from there,
               max_sub_array_sum = 29
0 votes
0 votes

With close observation, we can find the largest possible sum of the sub-array i.e. 29

Answer:

Related questions

29 votes
29 votes
4 answers
1
24 votes
24 votes
8 answers
2
Arjun asked Feb 7, 2019
17,139 views
The following C program is executed on a Unix/Linux system :#include<unistd.h int main() { int i; for(i=0; i<10; i++) if(i%2 == 0) fork(); return 0; }The total number of ...
13 votes
13 votes
4 answers
3
Arjun asked Feb 7, 2019
9,567 views
Consider the following C program :#include<stdio.h int jumble(int x, int y){ x = 2*x+y; return x; } int main(){ int x=2, y=5; y=jumble(y,x); x=jumble(y,x); printf("%d \n"...
17 votes
17 votes
3 answers
4