Solution to Maximum Subarray in linear-time algorithm with time complexity is O(n)

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">This algorithm realises the searching method for maximum subarray by changing the initial value when the sum is below 0.</span>
           

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">The C++ code shows as follow:</span>
           

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">
</span>
           

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);"></span><pre name="code" class="cpp">#include<iostream>
#include<vector>
using namespace std;

int MaxSum(vector<int>& a){
	int n=a.size();
	vector<int>::iterator it=a.begin();
	int max=*it;
	int sum=0;
	for(int cnt=0; cnt<n; cnt++){
		if(sum>0)
			sum += *it;
		else
			sum = *it;
		if(sum>max)
			max = sum;
		it++;
	}
	return max;
}

int main(){
	vector<int> vec;
	int a[]={-1,-2,-4,-10,-4,-7,-2,-5};
	vec.insert(vec.begin(),a,a+8);
	cout<<MaxSum(vec)<<endl;
	return 0;
}