Java箔方怏嶄銭偬n倖圷殆聞凪才恷寄
扮寂:2011-01-22 javaeye yoyo08
公協匯倖方怏?箔竃方怏嶄銭偬議匯乂圷殆聞凪才議峙恷寄。泌惚侭嗤圷殆脅葎屎方??隼屁倖方怏軸葎侭箔議。泌惚侭嗤圷殆議峙葎減方?夸侭箔議恷寄峙葎0.
宸頁壓園殻帷艨貧心欺議?凪扮寂鹸墫業喇O(n3)受葎O(n)阻。
java旗鷹
package cn.lifx.test;
public class MaxSum
{
public static void main(String[] args)
{
int[] arr = new int[]{31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
MaxSum ms = new MaxSum();
ms.Max(arr);
ms.Max2(arr);
ms.Max3(arr);
int max = ms.Max4(arr, 0, arr.length-1);
System.out.println("Max sum is " + max);
ms.Max5(arr);
}
//圭隈1: 扮寂鹸墫業葎O(n*n*n)
public void Max(int[] arr)
{
int max = 0;
int sum = 0;
int left = -1;
int right = -1;
for(int i=0; i<arr.length; i++)
{
for(int j=i; j<arr.length; j++)
{
sum = 0;
for(int k=i; k<=j; k++)
{
sum = sum + arr[k];
}
if(sum > max)
{
left = i;
right = j;
max = sum;
}
}
}
if(right > 0)
{
System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max);
}
else
{
System.out.println("Max sum is 0 .");
}
}
//圭隈2?扮寂鹸墫業葎O(n*n)
public void Max2(int[] arr)
{
int max = 0;
int sum = 0;
int left = -1;
int right = -1;
for(int i=0; i<arr.length; i++)
{
sum = 0;
for(int j=i; j<arr.length; j++)
{
sum = sum + arr[j];
if(sum > max)
{
left = i;
right = j;
max = sum;
}
}
}
if(right > 0)
{
System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is " + max);
}
else
{
System.out.println("Max sum is 0 .");
}
}
//圭隈3?扮寂鹸墫業葎O(n*n)
public void Max3(int[] arr)
{
int max = 0;
int sum = 0;
int left = -1;
int right = -1;
int[] temp = new int[arr.length+1];
temp[0] = 0;
for(int i=0; i<arr.length; i++)
{
temp[i+1] = temp[i] + arr[i];
}
for(int i=0; i<arr.length; i++)
{
for(int j=i; j<temp.length; j++)
{
sum = temp[j] - temp[i];
if(sum > max)
{
left = i;
right = j-1;
max = sum;
}
}
}
if(right > 0)
{
System.out.println("Max is from element " + left + "(" + arr[left] + ") to element " + right + "(" + arr[right] + "), max sum is "
|
