public int maxSubArray(int[] A) {
int newsum=A[0];
int max=A[0];
for(int i=1;i<A.length;i++){
newsum=Math.max(newsum+A[i],A[i]);
max= Math.max(max, newsum);
}
return max;
}
int maxSubArray(int *a, const int length)
{
int maxSumSubArray = ;
int sum_i = ;
for(int i=; i <length; i++)
{
sum_i = sum_i + a[i];
if(sum_i < ) sum_i = ;
else
{
if(sum_i > maxSumSubArray) maxSumSubArray = sum_i;
}
} //若是数组中的元素均为负值
if(sum_i==)
{
for(int i=; i < length; i++)
{
if(a[i] > maxSumSubArray) maxSumSubArray = a[i];
}
}
return maxSumSubArray;
}
还有一种是分治算法 自己写的 复杂度O（nlogn）
#include<iostream>
using namespace std;
int MaxSubArray(int *A,int low,int high){
if(low==high) return A[low];
int mid=(low+high)/;
int maxl=MaxSubArray(A,low,mid);
int maxr=MaxSubArray(A,mid+,high);
int maxleft=A[mid],maxright=A[mid+],maxsum;
maxsum=A[mid];
if(mid->=low)
for(int i=mid-;i>=low;i--){
maxsum=maxsum+A[i];
maxleft=max(maxsum,maxleft);
}
maxsum=A[mid+];
if(mid+<=high)
for(int i=mid+;i<=high;i++){
maxsum=maxsum+A[i];
maxright=max(maxsum,maxright);
}
int cross=maxleft+maxright;
return max(cross,max(maxl,maxr)); }
int main(){
int a[]={,-,,,-,};
cout<<MaxSubArray(a,,)<<endl;
return ;
}