#include <cstddef>
#include <iostream>

// Function declarations
void running_sum(
    int               array[],
    std::size_t const capacity
);

void print_array(
    int         const array[],
    std::size_t const capacity
);

int main();

// Function definitions
int main() {
    int array2[1]{
        15
    };

    int array3[10]{
         28, -6, 30, -1,  13,
         20, 11,  0, -21, -31
    };

    int array4[20]{
         35, -1, -22,  11,  -8,  10,  -8, -35, -10, 11,
         -5, 36, -49, -24,   8,  -1,  23,   8,  23, 24
    };

    print_array( nullptr, 0 );
    running_sum( nullptr, 0 );
    print_array( nullptr, 0 );
    std::cout << std::endl;

    print_array( array2, 1 );
    running_sum( array2, 1 );
    print_array( array2, 1 );
    std::cout << std::endl;

    print_array( array3, 10 );
    running_sum( array3, 10 );
    print_array( array3, 10 );
    std::cout << std::endl;

    print_array( array4, 20 );
    running_sum( array4, 20 );
    print_array( array4, 20 );

    return 0;
}

// Write a function that replaces each entry array[k]
// with the sum of the original entries
//
//     array[0] + array[1] + ... + array[k].
//
// For example,
//
//     3, 5, -2, 7
//
// should become
//
//     3, 8, 6, 13.
//
// One apparent problem is that you are replacing entries
// of the array with updated values, but those updated
// values are defined in terms of the original values.
//
// Can you take advantage of the updated values instead?

void running_sum(
    int               array[],
    std::size_t const capacity
) {
    // Enter your implementation here.
}

void print_array(
    int         const array[],
    std::size_t const capacity
) {
    if ( capacity > 0 ) {
        std::cout << array[0];

        for ( std::size_t k{ 1 }; k < capacity; ++k ) {
            std::cout << ", " << array[k];
        }
    }

    std::cout << std::endl;
}


































// One possible approach would be to make a copy of the
// original array.
//
// You could then calculate each running sum from the
// entries in the copy without worrying about entries in
// the original array having already been changed.
//
// There are two disadvantages:
//
//   1. You would require additional memory to store the
//      copy.
//
//   2. Calculating each running sum separately would
//      require many additions.
//
// For example, to calculate array[k], you would add
//
//     array[0] + array[1] + ... + array[k].
//
// Doing this independently for every k repeats much of
// the same work.
//
// Note that an array declared with a capacity that is
// determined only at run time, such as
//
//     int array_tmp[capacity];
//
// is not a standard C++ built-in array.


































// Another possibility is to start at the end of the
// array.
//
// For each index k, you could add all the preceding
// entries:
//
//     array[k] += array[0];
//     array[k] += array[1];
//             ...
//     array[k] += array[k - 1];
//
// Working backward means that these preceding entries
// still contain their original values.
//
// This works conceptually, but it again performs many
// unnecessary additions.
//
// Can you find a solution that requires only one pass
// through the array?




































// Notice what happens if you work forward:
//
//     array[1] += array[0];
//
// Now array[1] contains
//
//     original array[0] + original array[1].
//
// Next:
//
//     array[2] += array[1];
//
// Since array[1] already contains the sum of the first
// two original entries, array[2] now contains
//
//     original array[0]
//       + original array[1]
//       + original array[2].
//
// The same reasoning continues through the array.
//
// Thus, each previously calculated running sum contains
// exactly the information needed to calculate the next
// running sum.




































// One solution:

/*
void running_sum(
    int               array[],
    std::size_t const capacity
) {
    for ( std::size_t k{ 1 }; k < capacity; ++k ) {
        array[k] += array[k - 1];
    }
}
*/