Part 2.

Reminders:

  MS = Maximal Sum
  CS = Contiguous Subsequence 
int A[] =
 { 2, -3, 1, 2, -2, 4, -2, -3, -6, 4, -5, 3, -2, 3, -1, -1, 1, 3, -6, 2, -4, 2, -1, 2 };
// 0   1  2  3   4  5   6   7   8  9  10 11  12 13  14  15 16 17  18 19  20 21  22 23

Now for the tricky bit.

There are many techniques that can be tried out when you want to find a better,
simpler, or faster solution to a problem. You never know in advance which (if any)
will work.

Two to consider are making a problem more general, and its opposite, making a
problem more specific.

Our problem is quite general: the MS-CS could be anywhere in the array. So let's
try a less general version.

Attempt 1: What is the MS-CS that starts at exactly position P, and ends at
           exactly position Q?
   That is useless. When the start and end position are both given, there
   is only one possible CS, so asking which one has the maximal sum is pointless.

So attempt 1 went too far. Now we'll try something a little less specific.

Attempt 2: What is the MS-CS that starts exactly at position P?

Here the starting point is given, but the ending point could be anywhere between
P and N-1, so there is something to think about.

The MS-CS starting at position P (the MS-CS-S(P)) must, by definition, include 
item A[P]. We just don't know how many more items it might contain. If we did 
know how many more items beyond A[P] it contained, we would know exactly what 
the whole sequence is.

How many items beyond A[P] itself does MS-CS-S(P) contain? is it 0 or 1 or 2
or 3 or 4 or 5 or 6 or 7 or ... or N-P?

Lots and lots of very specific little questions. This might be an opportunity
to try out the other technique, making the problem more general. This
technique is more likely to be helpful in exactly this sort of situation.
There are lots of possible numeric solutions, 0 or 1 or 2 or 3 or 4 ...
This can easily be generalised into just two:
          is it zero or is it more than zero
     or   is it none or is it some.

Repeating the question:
   How many items beyond A[P] itself does MS-CS-S(P) contain?
   it could be none
   or it could be some
the answer has to be one of those two. We can tackle them separately.

Case 1. MS-CS-S(P) contains no more items
   in this case the sequence is just { A[P] }
   and the sum of the sequence is just the number A[P].

Case 2. MS-CS-S(P) contains some more items
   ( we should note that case 2 is impossible if there are no more
     items to consider, that is if P = N-1 )
   in this case the sequence starts with { A[P], A[P+1], ... } but we
     don't know how long it is.
   But a Contiguous Sequence that starts with A[P] and A[P+1] is exactly
     the same thing as adding A[P] to a Contiguous Sequence that starts
     with A[P+1].
   The sum of that sequence must be A[P] + (the sum of a CS starting at P+1)
   Of all the possible CSs starting at P+1, which is going to make that
   sum the biggest? The maximal one of course. The MS-CS-S(P+1).

In case 1, MS-CS-S(P) is just A[P].
in case 2, MS-CS-S(P) is A[P] plus MS-CS-S(P+1)
and those are the only possibilities.

Which of those cases is the correct one? We're after the maximal sum,
so it must be the biggest one.

In almost-C++

    MS_CS_S(int P) is
    { 
      case1 = A[P];
      case2 = A[P] plus MS_CS_S(P+1);
      if (case1 > case2)
        the answer is case1;
      else
        the answer is case2;
    }

Noting that X is greater than X + Y exactly when Y is negative, it is
simplified to

    MS_CS_S(int P) is
    { 
      Y = MS_CS_S(P+1);

      if (Y < 0)
        the answer is A[P];
      else
        the answer is A[P] plus Y;
    }

to make it strictly correct, we must take into account the observation
that case 2 is impossible if P = N-1:

    MS_CS_S(int P) is
    { 
      if (P == N-1)
        the answer is A[P];

      Y = MS_CS_S(P+1);

      if (Y < 0)
        the answer is A[P];
      else
        the answer is A[P] plus Y;
    }

I have been writing "plus" instead of "+", and "the answer is" instead
of "return", and didn't give Y a prioper declaration like "int Y" because
we have really been talking about finding out what the maximal sequence
is (i.e. which particular numbers make up the sequence), not just finding
out what its sum is.

If we'd settle with just knowing the sum, this can be converted into
a complete program very easily. You could just copy and paste this, and
it will run.

    #include <iostream>

    int A[] =
    { 2, -3, 1, 2, -2, 4, -2, -3, -6, 4, -5, 3, -2, 3, -1, -1, 1, 3, -6, 2, -4, 2, -1, 2 };
    const int N = 24;

    int MS_CS_S(int P)
    { 
      if (P == N-1)
        return A[P];
      int Y = MS_CS_S(P+1);
      if (Y < 0)
        return A[P];
      else
        return A[P] + Y;
    }

    void main()
    { for (int i=0; i<N; i+=1)
      { int S = MS_CS_S(i);
        cout << "maximal sum starting at position " << i << " is " << S << "\n"; } }

The recursion seems almost natural, doesn't it?

But let's get rid of it anyway.

Look at the function again. To work out what MS_CS_P(P) is, you have to know
what MS_CS_P(P+1) is:

   To work out MS_CS_P(0) you need to know MS_CS_P(1)
   To work out MS_CS_P(1) you need to know MS_CS_P(2)
   To work out MS_CS_P(2) you need to know MS_CS_P(3)
   To work out MS_CS_P(3) you need to know MS_CS_P(4)
   To work out MS_CS_P(4) you need to know MS_CS_P(5)
   ...
   ...
   ...
   To work out MS_CS_P(N-4) you need to know MS_CS_P(N-3)
   To work out MS_CS_P(N-3) you need to know MS_CS_P(N-2)
   To work out MS_CS_P(N-2) you need to know MS_CS_P(N-1)
   To work out MS_CS_P(N-1) you don't need anything else

In retrospect, we should have stared with N-1 and just worked backwards.
A little loop noting that at position N-1 the answer is A[N-1], and
workind backwards to position 0 would only need to remember what the
answer was the previous time around the loop.

   void main()
   { int Answer = A[N-1];
     int Previous = Answer;
     cout << "at position " << N-1 << " the sum is " << Answer << "\n";

     int Position = N-2;
     while (Position >= 0)
     {
       if (Previous < 0)
         Answer = A[Position];           
       else
         Answer = A[Position] + Previous;

       cout << "at position " << Position << " the sum is " << Answer << "\n";

       Previous = Answer;
       Position -= 1; } }

You might notice that the variable "Previous" turned out to be completely
useless. We could have been directly updating Answer instead.

And instead of printing the answer for each position, we could simply remember
the best answer seen so far (and what position it was found at).

   void main()
   { int Answer = A[N-1];
     int BestAnswer = Answer;
     int BestPosition = N-1;

     int Position = N-2;
     while (Position >= 0)
     {
       if (Answer < 0)
         Answer = A[Position];           
       else
         Answer += A[Position];

       if (Answer > BestAnswer)
       { BestAnswer = Answer;
         BestPosition = Position; }

       Position -= 1; }

     cout << "position " << BestPosition << " has best sum " << BestAnswer << "\n"; }

The thing to note is that this program has just one simple loop that runs from
N-1 down to 0, doing a very small simple thing each time. The time it takes will
depend on N, not N squared or N cubed, just N.

We have transformed a dreadful Cubic algorithm into a nice Linear algorithm
just by logic and experiment.

And finally, if we know where the MS-CS starts and what it adds up to, we can
print out the sequence itself. Just start at the known position, and continue
printing things until they add up to the known sum.

     cout << "position " << BestPosition << " has best sum " << BestAnswer << "\n";
     Answer = 0; 
     Position = BestPosition;
     while (Answer < BestAnswer)
     { cout << " " << A[Position];
       Answer += A[Position];
       Position += 1; }
     cout << "\n"; }

And that's the end of that.