I have an exercise to solve: "Write an efficient C program to find the largest sum of contiguous subarray within an one-dimensional array of integers. A contiguous subarray of an array is defined as the sequence of elements that are in any continuous set of indices that are valid within an array.
Lets take an example of an array {5,-3, 4}. Possible contiguous subarray combinations are {5}, {-3}, {4}, {5,-3}, {-3,4} and {5,-3,4}. Note that {5,4} is not a valid subarray as the indices of 5 and 4 are not continuous. The contiguous subarray {5,-3,4} has the largest sum 6."
I tried to solve it but I realized I did not even understand the problem since if I have an array of 5 different values, the result should be 10, while I would have said 15 (5 different elements + 1 as a whole + 4 elements if taken 2 by 2 + 3 if taken 3 by 3 + 2 if taken 4 by four).
Before trying to code it (in C), I would like to know if anyone can help me understanding the problem itself.
This is how I would solve the problem. This is not necessarily the optimal solution, but I believe it should work.
Consider the array: {1, -2, 3, 5, -4} and consider how you could write all sub-arrays by hand:
Looks like the largest sum is 8.
You should see a pattern here I started with the length of the array, 5 in this case, and decreased it by one till I processed one-element arrays. I also started with the zeroth element of the array and attempted to make a valid array given the length. For example, if I was working with the four element arrays, starting at array element 0, it could make a sub array via array[0] -> array[3] and array[1]->array[4] (this is array slicing, some languages like Python have explicit notation for performing an array slice, C doesn't). After generating each slice, sum the elements, when done look for the max.
Now, I'd code this something like this
int main(void)
{
int array[] = {1, -2, 3, 5, -4};
int max = -1; // will hold largest sum
int len = sizeof(array)/sizeof(int); // C-idiom to find length of array
for(int slen = len; slen > 0; slen--) // loop for length of sub-arrays
{
for(int jdx = 0; jdx+slen <= len; jdx++) // looping over elements in original array
{
int temp = calcSum(array, jdx, slen);
if(temp > max)
max = temp;
}
}
printf("maximum sum of sub-array is: %d\n", max);
}
now all that is left is to write the calcSum function. It takes three parameters - the first is the original array, the second is where the sub-array starts and the this is the length of the sub array.
int calcSum(int* array, int start, int len)
{
int sum = 0;
printf("[%d:%d]: {", start, start+len);
for(int ndx = 0; ndx < len; ndx++)
{
printf("%d,", array[start+ndx]);
sum = sum + array[start+ndx];
}
printf("} the sum is %d\n", sum);
return sum;
}
I sprinkled a few printf's in there so you can see what is going on as the program loops. My slice notation is [start:length] so [1:3] would be the array that is starting at index one, and having a length of 3 (i.e array[1], array[2], array[3]).
Compiling the above as gcc -std=c99 -pedantic -Wall test.c -o temp and executing this, yields:
D:\Users\******\GNUHome>temp.exe
[0:5]: {1,-2,3,5,-4,} the sum is 3
[0:4]: {1,-2,3,5,} the sum is 7
[1:4]: {-2,3,5,-4,} the sum is 2
[0:3]: {1,-2,3,} the sum is 2
[1:3]: {-2,3,5,} the sum is 6
[2:3]: {3,5,-4,} the sum is 4
[0:2]: {1,-2,} the sum is -1
[1:2]: {-2,3,} the sum is 1
[2:2]: {3,5,} the sum is 8
[3:2]: {5,-4,} the sum is 1
[0:1]: {1,} the sum is 1
[1:1]: {-2,} the sum is -2
[2:1]: {3,} the sum is 3
[3:1]: {5,} the sum is 5
[4:1]: {-4,} the sum is -4
maximum sum of sub-array is: 8
N.B. I compiled this with gcc version 4.8.3 (from mingw) on a Windows 7 Professional.