Largest subarray max sum problem

Question:
Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.
some numbers are negative.
Time Complexity: O(n)
Answer:
void maxsumofsubarray(int* array, int len) {
int curMax = 0;
int mi = -1;
int mj = -1;
int max;
bool max_init = false;
for (int i = 0; i < len; i++) {
if (curMax <= 0) {
curMax = array[i];
mi = i;
mj = i;
} else {
curMax += array[i];
}
if (!max_init || max < curMax) {
max = curMax;
mj = i;
max_init = true;
}
}
for (int i = mi; i <= mj; i++) {
cout << array[i] << " ";
}
cout << endl;
cout << " max sub array sum is " << max << endl;
}

Comments

Popular posts from this blog

How to fix error : no module named sendgrid when try to use sendgrid python lib in PHP.

react-native run-android : sun.security.provider.cert path.SunCertPathBuilderException : unable to find valid certification path to req uested target

react-native run-android : do not build/update modified code(App.js)