Some Context: I am solving a problem from HackerRank regarding the contiguous subsequence and subset with largest sum on a series of integers. The algorithm may be correct or not, I'm not concerened about its correctness but rather the unusual behavior of my program, please continue reading.
input.txt:
1
6
2 -1 2 3 4 -5
Input Format:
number of testcases
number of integers (let that be n)
n space-sepearated integers
Correct Output (based on source):
10 11
Actual Output:
11 11
As you can see, the actual output does not match the correct output. I spent time manually performing the algorithm on the input using pen and paper before and after writing the program, and my computation seems to match the correct output (My algorithm may still not be correct). But afterwards, I attempted to use gdb to trace the program line by line and I found something unusual at the start of a function call to bestSum1.
GDB Output Snippet: (Go to the part near the end where I print integers[0] and show that the value changed when I passed it to a function.
(gdb) break main
Breakpoint 1 at 0x4005fe: file maxsub.c, line 14.
(gdb) break bestSum1
Breakpoint 2 at 0x400745: file maxsub.c, line 33.
(gdb) run < input.txt
Starting program: /home/ken/Desktop/dynamic prog/maxsub < input.txt
Breakpoint 1, main () at maxsub.c:14
14 scanf("%d", &T);
(gdb) n
16 for (i = 0; i < T; i++) { // Each testcase
(gdb) n
17 scanf("%d", &N); // Get size of array
(gdb) n
18 int integers[N]; // Allocate memory
(gdb) n
20 for (j = 0; j < N; j++) { // Fill up array
(gdb) n
21 scanf("%d", &integers[j]);
(gdb) n
< SNIPPED PART > this is basically where for loop repeats N times
(gdb) n
20 for (j = 0; j < N; j++) { // Fill up array
(gdb) n
24 printf("%d %d\n", bestSum1(N, integers), bestSum2(N, integers)); // Print Answer
/** START TAKING A LOOK HERE, this is where the unusual thing happens: **/
(gdb) print integers[0] <---- INITIAL VALUE
$1 = 2
(gdb) print integers <---- ADDRESS OF ARRAY
$2 = 0x7fffffffdea0
(gdb) n
Breakpoint 2, bestSum1 (size=6, integers=0x7fffffffdea0) at maxsub.c:33
33 best_sum = - INFINITY, // Best Sum Found
(gdb) print integers[0] <---- VALUE CHANGED
$3 = -5
(gdb) print integers <---- SAME ADDRESS
$4 = (int *) 0x7fffffffdea0
(gdb)
Full Source Code :
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INFINITY INT_MAX
int bestSum1(int size, int integers[size]);
int bestSum2(int size, int integers[size]);
int compare(const void* p1, const void* p2);
int main() {
int T, N, // testcases (T) and array size (N)
i, j; // Declare loop counters
scanf("%d", &T);
for (i = 0; i < T; i++) { // Each testcase
scanf("%d", &N); // Get size of array
int integers[N]; // Allocate memory
for (j = 0; j < N; j++) { // Fill up array
scanf("%d", &integers[j]);
}
// bestSum1 gets strictly contiguous subsequence with largest sum
// bestSum2 gets subset of numbers with largest sum
printf("%d %d\n", bestSum1(N, integers), bestSum2(N, integers));
}
return 0;
}
int bestSum1(int size, int integers[size]) {
// CONTIGUOUS SUBSEQUENCE WITH LARGEST SUM
int curr_sum = 0, // Current Sum
best_sum = - INFINITY, // Best Sum Found
value, // Where we store value
i; // Loop Counter
for (i = 0; i < size; i++) {
value = curr_sum + integers[i];
if (value <= 0) {
curr_sum = 0;
} else if (value > best_sum) {
best_sum = value;
curr_sum = best_sum;
}
}
return best_sum;
}
int bestSum2(int size, int integers[size]) {
// NON-CONTIGUOUS SUBSEQUENCE WITH LARGEST SUM
qsort(integers, size, sizeof(int), compare);
int sum = -1,
i;
for (i = 0; i < size; i++) {
if (integers[i] > 0) {
sum += integers[i];
}
}
return sum == -1 ? integers[size - 1] : sum;
}
int compare(const void* p1, const void* p2) {
return *((int*) p1) - *((int*) p2);
}
So I want to know how to fix this and why this happens.
