Skip to content

Instantly share code, notes, and snippets.

@StabbyMcDuck
Last active August 29, 2015 14:19
Show Gist options
  • Save StabbyMcDuck/6b6da1942f0db7e5f6b9 to your computer and use it in GitHub Desktop.
Save StabbyMcDuck/6b6da1942f0db7e5f6b9 to your computer and use it in GitHub Desktop.
possible fix for subarray
typedef struct {
int left;
int right;
int sum;
} max_subarray;
max_subarray find_maximum_subarray(int A[], unsigned low, unsigned high) {
max_subarray suffixes[high - low];
suffixes[0].left = low;
suffixes[0].right = low + 1;
suffixes[0].sum = A[low];
for (int i = low + 1; i < high; i++) {
if (suffixes[i - 1].sum < 0) {
suffixes[i].left = i;
suffixes[i].right = i + 1;
suffixes[i].sum = A[i];
} else {
max_subarray *previous = &suffixes[i - 1];
suffixes[i].left = previous->left;
suffixes[i].right = i + 1;
suffixes[i].sum = previous->sum + A[i];
}
}
max_subarray *max = &suffixes[0];
for (int i = low + 1; i < high; i++) {
if (max->sum < suffixes[i].sum) {
max = &suffixes[i];
}
}
return *max;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment