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)
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;
}
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;
}
No comments:
Post a Comment