gistfile1.txt

//
//  reginaImhoff.cpp
//  cs325project1
//
//  Created by Regina Imhoff on 4/21/15.
//
//

#include "algorithm4.h"
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <new>


struct maxSubArrayAndSum{
    int *maxSubArray;
    size_t size;
    int sum;
};

struct maxSubArrayAndSum *maxSubArray(int *a, size_t size){
    struct maxSubArrayAndSum *result = NULL; // null to handle when no array is found
    int max_so_far = 0;
    int max_ending = 0;
    int max_start_index = 0;
    int max_end_index;
    int index_start = 0;
    
    for(int i = 0; i < size; i++){
        if(max_ending + a[i] < 0){
            index_start = i + 1;
            max_ending = 0;
        } else {
            max_ending += a[i];
        }
        
        if(max_ending > max_so_far){
            max_so_far = max_ending;
            max_start_index = index_start;
            max_end_index = i;
        }
    }
    
    if(max_start_index <= max_end_index){
        result = new struct maxSubArrayAndSum;
        size_t maxSubArraySize = max_end_index - max_start_index + 1; //if end and start are the same size, you still want at least 1 here!
        result->maxSubArray = new int [maxSubArraySize];
        result->size = maxSubArraySize;
        
        std::copy(a + max_start_index, a + max_end_index + 1, result->maxSubArray);
    }
    return result;
}

int main(){
    int dummy[] = {31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
    
    struct maxSubArrayAndSum *resultValue = maxSubArray(dummy, 10);
    /*
    for(int i = 0; i < resultValue->size; i++){
        std::cout << i << std::endl;
    }
    
    std::cout << resultValue->sum << std::endl;
     */
    return 0;
}