# Maximum Subarray

Question:

http://www.lintcode.com/en/problem/maximum-subarray/

Given an array of integers, find a contiguous subarray which has the largest sum.

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;
}
```