之前找别人的解体方案的时候总是习惯性的找有文字描述的，今天看到这个Gas Station的题目，文字说明到让我有点糊涂，代码加公式的描述竟然更好理解。
这篇博客里面说Gas Station的问题其实是最大子段和 ，只不过是一个循环的。然后就Google了一下最大子段和的求法，发现这个最大子段和详解（N种解法汇总） 里面描述了各种解法，非常好。不过其中分治发和动态规划发的文字描述虽然很详细却并不好理解，而这篇 文章里面几个公式加代码让我一下就看懂了。具体就是：
问题：
给定n个整数（可能为负数）组成的序列a1,a2,a3,…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当（a1,a2,a3,a4,a4,a6）=(-2,11,-4,13,-5,-2)时，最大子段和为20。
分治法：
将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况: (1)a[1n]的最大子段和与a[1n/2]的最大子段和相同 (2)a[1n]的最大子段和与a[n/2n]的最大子段和相同 (3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n T(n)=2T(n/2)+O(n) T(n)=O(nlogn)
int MaxSum_DIV(int *v,int l,int r)
{
int k,sum=0;
if(l==r)
return v[l]>=0?v[l]:0;
else
{
int center=(l+r)/2;
int lsum=MaxSum_DIV(v,l,center);
int rsum=MaxSum_DIV(v,center+1,r);
int s1=0;
int lefts=0;
for (k=center;k>=l;k--)
{
lefts+=v[k];
if(lefts>s1)
s1=lefts;
}
int s2=0;
int rights=0;
for (k=center+1;k<=r;k++)
{
rights+=v[k];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<lsum)
sum=lsum;
if(sum<rsum)
sum=rsum;
}
return sum;
}
动态规划法：
b[j]=max{a[i]+…+a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。 由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为: b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。 T(n)=O(n)
int MaxSum_DYN(int *v,int n)
{
int sum=0,b=0;
int i;
for (i=1;i<=n;i++)
{
if(b>0)
b+=v[i];
else
b=v[i];
if(b>sum)
sum=b;
}
return sum;
}
这个题要用反证法来理解。算法：
代码：
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int N = gas.length, startIndex = -1;//为什么是-1 ？
int sum = 0, total = 0;
for(int i = 0; i < N; i++){
sum += (gas[i] - cost[i]);
total += (gas[i] - cost[i]);
if(sum < 0){
startIndex = i;
sum = 0;
}
}
return total >= 0 ? startIndex + 1 : -1;
}
}