3 Joe Coder is investing in stocks and he is analyzing profi

3) Joe Coder is investing in stocks and he is analyzing profits from the last period by observing the gains and losses his investments generated. You must write a C program named a5q3.c to help him with the analysis.

He prepared input in the following format: Each line of input starts with a number n that gives the number of gains or losses an stock made during the last period, followed by the list of those gains and losses. He likes to be able to analyze different periods: they could be months in a year or serveral years, days over a period, and so on. For this reason, you program must handle varying lenghts of sequences of these numbers. More precisely, he expressed each gain as a positive number and a loss as a negative number, and a zero would be no gain and no loss. Joe would like to find out when was the perfect time to buy that stock and to sell that stock in that period if he were to buy it only once and later sell it only once. For example, in the following sequence of gains and losses:

it should be obvious that the best time was to buy the stock after the loss -3.4 and before gain 2.0, and sell it just before -1.0, so the net gain would be 3.0. However if we had the sequence:

it is the best idea to buy it before 2.0 and keep it until the end, so the net gain would be: 2.0+1.01.0+1.1 = 3.1.

Your program must read such sequences and for each of them calculate the maximal gain possible (which could be a loss), print it, and also print the part of the sequence that generates that total gain or loss.

Implementation note: You can store the numbers in an array, but to obtain full points you must use pointers to iterate through array. You must use type double for gains and losses.

Input:

Several sequences are given in the input. Each sequence starts with the sequence length n, followed by n numbers representing gains and losses. The end of input is marked by number 0 used for n.

Output:

For each input sequence you must print one line of output starting with the maximal total gain possible, at the precision of two decimal places, followed by a colon (:), followed by the list of gains and losses that produce that total gain. The numbers in the list must be separated by one space and printed also with two decimal places of precision. If several lists of gains and losses may produce the same maximal total gain, then you must choose one with the earliest (leftmost) start, and if several of them have the same start then choose the shortest one.

Sample Input:

Sample Output:

Solution

Following c code should do the job. The key point was that we need to find maximum sum contiguous subarray in the given array:

#include <stdio.h>
#include <limits.h>

typedef struct{
double retVal;
int lIndex;
int rIndex;
}result;

result maxCrossingSum( double arr[], int low, int mid, int high){
    double sum = 0;
    double left_sum = INT_MIN, right_sum= INT_MIN;
    int li=mid, ri=mid+1;
  
    int i = mid;
    for(; i >= low; i--){
        sum = sum + arr[i];
        if (sum > left_sum){
          left_sum = sum;
          li = i;
        }}

    sum = 0;
    i = mid+1;
    for(; i <= high; i++){
        sum = sum + arr[i];
        if (sum > right_sum){
          right_sum = sum;
          ri = i;
        }}
    result r;
    r.retVal = left_sum + right_sum;
    r.lIndex = li;
    r.rIndex = ri;
    return r;
}

result maxSubArraySum( double arr[], int low, int high)
{
   if (low == high){
      result r;
      r.retVal = arr[low];
      r.lIndex = low;
      r.rIndex = high;
      return r;
   }
   int mid = (low + high)/2;
    result p = maxSubArraySum(arr, low, mid);
    result q = maxSubArraySum(arr, mid+1, high);
    result r = maxCrossingSum(arr, low, mid, high);
    if(p.retVal < q.retVal ){ p = q; }
    if(p.retVal < r.retVal ){ p = r; }
    return p;
}

int main(){
   int n;
   double arr[1000];
   while(1){
     scanf(\"%d\",&n);
     if( n == 0 ){ break; }
     int i = 0;
     for(; i < n; i++){
      scanf(\"%lf\",&arr[i]); }
     result r = maxSubArraySum(arr, 0, n-1);
     printf(\"%.2f:\", r.retVal);
     for(; r.lIndex <= r.rIndex; r.lIndex++ ){
      printf(\" %.2f\", arr[r.lIndex] );
     }
     printf(\"\ \");
   }
   return 0;
}