编程之美求数组的子数组之和的最大值

一个有N个整数元素的一位数组（A[0]，A[1]，A[2]，...，A[n-1]），这个数组当然有很多子数组，那么子数组之和的最大值是什么？

比如 -2 5 3 -6 4 -8 6 的最大子数组是 5 3。

法一：

挨个遍历查找：

int maximum=-INF;  
int sum;  
for(int i=0;imaximum)  
        maximum=sum;  
     
   }  
return maximum;  
  
}  

int maximum=-INF;
int sum;
for(int i=0;imaximum)
maximum=sum;
   
   }
return maximum;

}

     法二：

采用DP的方法，


 
int max(int x,int y)  
{  
    return (x>y) x:y;  
  
}  
  
int MaxSum(int*A,int n)  
{  
    
  Start[n-1]=A[n-1];  
  All[n-1]=A[n-1];  
  for(i=n-2;i>=0;i--)  
  {  
    Start[n-1]=max(A[i],A[[i]+Start[i+1]);  
    All[i]=max(Start[i],All[i+1]);  
      
    
  }  
  return All[0];  
  
}  

int max(int x,int y)
{
return (x>y) x:y;

}

int MaxSum(int*A,int n)
{
  
  Start[n-1]=A[n-1];
  All[n-1]=A[n-1];
  for(i=n-2;i>=0;i--)
  {
    Start[n-1]=max(A[i],A[[i]+Start[i+1]);
All[i]=max(Start[i],All[i+1]);

  
  }
  return All[0];

}

编程之美 求数组的子数组之和的最大值