サブ配列の最大和
2462 ワード
public class SubarrayMax {
public static void main(String[] args)
{
int[] a = {8,-1,-1,5,3,2,8,-9};
System.out.println(method1(a,a.length));
System.out.println(method2(a,a.length));
System.out.println(method3(a,a.length));
System.out.println(method4(a,0,a.length-1));
}
//
public static int method4(int a[],int left,int right){
if(left==right){
return max(a[left],0);
}
int middle=(left+right)/2;
// (A[0],...A[n/2-1]) A[n/2-1]
int lmaximum=0;
int lsum=0;
for(int i=middle;i>=left;i--){
lsum+=a[i];
if(lsum>lmaximum)
lmaximum=lsum;
}
// (A[n/2],...,A[n-1]) A[n/2]
int rmaximum=0;
int rsum=0;
for(int i=middle+1;i<=right;i++){
rsum+=a[i];
if(rsum>rmaximum)
rmaximum=rsum;
}
return max(lmaximum+rmaximum,max(method4(a,left,middle),method4(a,middle+1,right)));
}
public static int method3(int[] a,int n)
{
int nstart = a[n-1];
int nall = a[n-1];
for(int i=n-2;i>=0;i--)
{
if(nstart<0)
nstart = 0;
nstart +=a[i];
if(nstart>nall)
nall = nstart;
}
return nall;
}
//start a[i]
//all
public static int method1(int a[],int n)
{
int[] start = new int[n];
int[] all = new int[n];
start[n-1] = a[n-1];
all[n-1] = a[n-1];
for(int i=n-2;i>=0;i--)
{
start[i] = max(a[i],a[i]+start[i+1]);
all[i] = max(start[i],all[i+1]);
}
return all[0];
}
//
public static int method2(int[] a,int n)
{
int nstart = a[n-1];
int nall = a[n-1];
for(int i=n-2;i>=0;i--)
{
nstart = max(a[i],nstart+a[i]);
nall = max(nstart,nall);
}
return nall;
}
private static int max(int i, int j) {
return i>j?i:j;
}
}