/* Challenge:Maximum subarray sum The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers: maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]) # should be 6: [4, -1, 2, 1] Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead. Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray. */ /* Input: length element1 element2... For example: 9 -2 1 -3 4 -1 2 1 -5 4 */ #include #include #include #include //#define DEBUG using namespace std; void formResultStr(char* res, int* a, int beg, int end, int s) { sprintf(res, "%d: [%d", s, a[beg]); for (int i = beg + 1; i <= end; i++) sprintf(res + strlen(res), ", %d", a[i]); sprintf(res + strlen(res), "]\n"); } int main() { /* int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4} l = 9; */ int l, i, sMax; cin >> l; // length of array; int* arr = (int*) malloc(sizeof(int) * l); for (i = 0; i < l; i++) cin >> arr[i]; // elements char resultStr[300]; bool isPos = arr[0] > 0; bool isNeg = arr[0] < 0; int s = arr[0]; for (i = 1; i < l; i++) { if (arr[i] > 0) isPos = true; if (arr[i] < 0) isNeg = true; s += arr[i]; } if (! isNeg) { formResultStr(resultStr, arr, 0, l - 1, s); cout << resultStr; return 0; } else if (! isPos) { cout << 0 << ": []"; return 0; } int maxBeg = 0, maxEnd = l - 1, maxS = s; int b, e, subL; b = 0; while (b < l) { //e = (b = 0) + subL - 1; s = 0; for (i = b; i < l; i++) { s += arr[i]; if (s > maxS) { maxBeg = b; maxEnd = i; maxS = s; } #ifdef DEBUG formResultStr(resultStr, arr, b, i, s); cout << resultStr; #endif } s -= arr[b]; b++; if (b == l) break; for (i--; i >= b; i--) { if (s > maxS) { maxBeg = b; maxEnd = i; maxS = s; } #ifdef DEBUG formResultStr(resultStr, arr, b, i, s); cout << resultStr; #endif s -= arr[i]; } b++; } formResultStr(resultStr, arr, maxBeg, maxEnd, maxS); cout << resultStr; return 0; }