最大连续子数组和

Maximum Contiguous Subarray

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

数组 $A$ 长度 $n$ （可为负）。求

\max_{1\le i\le j\le n}\sum_{x=i}^j A[x].

Array $A$ length $n$ , possibly negative. Find $\max_{1\le i\le j\le n}\sum_{x=i}^j A[x].$

解析

Kadane 算法可在 $O(n)$ 时间完成：

double maxSubarray(const double A[], int n){
  double T=A[0], Vmax=A[0];
  double Tmin = (T<0)?T:0;
  for(int i=1;i<n;i++){
    T += A[i];
    if(T - Tmin> Vmax) Vmax=T-Tmin;
    if(T< Tmin) Tmin=T;
  }
  return Vmax;
}

Original Explanation

Kadane’s in $O(n)$ :

double maxSubarray(const double A[], int n){
  double T=A[0], Vmax=A[0];
  double Tmin = (T<0)?T:0;
  for(int i=1;i<n;i++){
    T += A[i];
    if(T - Tmin> Vmax) Vmax=T-Tmin;
    if(T< Tmin) Tmin=T;
  }
  return Vmax;
}