Max Sum. The following is an instance.
a) (-2，11，-4，13，-5，-2)
思路：
最大子段和：给定一个序列（元素可正可负），找出其子序列中元素和最大的值。
1.令b[j]表示以位置 j 为终点的所有子区间中和最大的一个
2.子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中
3.如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含
4.如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大
则所求的最大子段和为：
由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。
public class Q4_Max_Sum {
public static void main(String[] args)
{
int arr[] = {-2,11,-4,13,-5,-2};
System.out.println("子序列和最大子段和分别为：");
System.out.print(Maxsum(arr));
System.out.println();
//System.out.print(MaxsumDP(arr));
}
public static int MaxsumDP(int[] arr)
{
int n = arr.length;
int[] b = new int[n];
int max =0;
for(int j=0;j<n;j++)
{
if (j==0)
{
b[j] = arr[j];
}
else if(j>=1)
{
if(b[j-1]>0)
b[j] = b[j-1] + arr[j];
else
b[j] = arr[j];
}
}
max = b[0];
for(int i=0;i<n;i++)
{
if(max<b[i])
max = b[i];
}
return max;
}
public static int Maxsum(int[] arr)
{
int head,tail,sum,max,i,j,x;
head = tail = x =0;
max = sum = arr[0];
for(i=1;i<arr.length;i++)
{
if((sum+arr[i])<arr[i])
{
x=i;
sum = arr[i];
}else {
sum +=arr[i];
}
if(sum>max)
{
max = sum;
tail = i;
head = x;
}
}
for(i=head;i<=tail;i++)
{
System.out.print(arr[i]);
System.out.print(' ');
}
System.out.println();
return max;
}
}