/*---------------------------------------------------------------------------
File name: max_subseq2.cpp
Author: HJin

The problem is called the max-subsequence problem. This implementation
compiles and runs under VS2005.

Sample ouput:

3 73 -95 42 43 29 -30 -87 74 -53 22 74 -91 -1 -27 -8 -14 26 -67 -74
max subsequence starts at index 8
max subsequence ends at index 11
74-53+22+74 = 117
117

Reference:

Mark Allen Weiss: Data Structures and Algorithm Analysis in C

HJin's apology:

Working on a system which has no Chinese input. What a pain!
*/

#include <iostream>
#define DIM(x) sizeof((x)) /sizeof ((x)[0])

using namespace std;

/**
max_subseq() does not work for an array of all negative numbers.
I will leave it for you to refine it.
*/
int max_subseq(int *a, int n);

/**
Print the soln to the max-subseq problem.
*/
void printSoln(int *a, int best_i, int best_j, int maxSum);

/**
Print an array of size n.
*/
void print(int *a, int n);

int main(int argc, char** argv)
{
int a[] = {3, 73, -95, 42, 43, 29, -30, -87, 74, -53, 22, 74, -91, -1, -27, -8, -14, 26, -67, -74};

print(a, DIM(a));
cout<<max_subseq(a, DIM(a))<<endl;

return 0;
}

void printSoln(int *a, int best_i, int best_j, int maxSum)
{
int k;

// print out messages
cout<<"max subsequence starts at index "<<best_i<<endl;
cout<<"max subsequence ends at index "<<best_j<<endl;
cout<<a[best_i];

for(k=best_i+1; k<=best_j; ++k)
if(a[k] >=0 )
cout<<"+"<<a[k];
else
cout<<a[k];

cout<<" = "<<maxSum<<endl;
}

/** The algorithm uses O(1) space and runs in O(n) time and it is online.
The following is Mark Allen Weiss's comment:

An extra advantage of this algorithm is that it makes only one pass through
the data, and once a[i] is read and processed, it does not need to be
remembered. Thus, if the array is on a disk or tape, it can be read
sequentially, and there is no need to store any part of it in main memory.
Furthermore, at any point in time, the algorithm can correctly give an
answer to the subsequence problem for the data it has already read (the
other algorithms do not share this property). Algorithms that can do
this are called on-line algorithms. An on-line algorithm that requires
only constant space and runs in linear time is just about as good
as possible.

maxSum --- stores the max sum of the max-subseq
best_i --- stores the starting index of the max-subseq
best_j --- stores the ending index of the max-subseq
*/
int max_subseq(int *a, int n)
{
int maxSum = 0;
int thisSum = 0;
int bestStart = -1;
int bestEnd = -1;
int i = 0;
int j;

/**
to make it work for all kinds of input, do some extra work
before this loop.
*/
for (j = 0; j<n; ++j)
{
thisSum += a[j];

if ( thisSum > maxSum )
{
maxSum = thisSum;
bestStart = i;
bestEnd =j;
}

if ( thisSum < 0 )
{
thisSum = 0;
i = j+1;
}

}

// print the soln
printSoln(a, bestStart, bestEnd, maxSum);

return maxSum;
}

void print(int *a, int n)
{
for(int i=0; i<n; ++i)
cout<<a[i]<<" ";
cout<<endl;
}