程序功能:
给定一个数组,当中有正负数,求当中的一段“子数组”(即任意长度,连续的数字),使得这个“子数组”的和是所有“子数组”和中最大的, 如给定的数组为12, -8, 5, 66, -21, 0 ,35, -44,7,则最大的和的子数组为{12, -8, 5, 66, -21, 0 ,35},最大的和为89.
实现:分治法
语言:c 和 java
运行环境:BC和JDK
运行结果:在c下结果正确(结果55),但在java下(结果101)不正确
问题:这是为什么?
c code:
#include <stdio.h>#define MIN_INT_UNM -32768int s[] = {12,-8,5,66,-21,0,35,-44,7};int divide(int low,int high)
{
int value;
int lowValue;
int highValue;
int maxValue;
int mid;
int i,j; if (low > high)
return MIN_INT_UNM;
if (low == high)
return s[low]; mid = (low + high)/2;
lowValue = divide(low,mid);
highValue = divide(mid + 1,high);
maxValue = lowValue < highValue ? highValue : lowValue; for (i = mid;i >= low;--i) {
value = s[i];
for (j = i + 1;j <= high;++j) {
value += s[j];
if (value > maxValue)
maxValue = value;
}
} return maxValue;
}void main(void)
{
int max = s[0];
int len = sizeof(s) / sizeof(s[0]) - 1; max = divide(0,len); printf("%d\n",max);
}
java code:
public class Test2
{
static int s[] = {12,-8,5,66,-21,0,35,-44,7};
static final int MIN_INT_UNM = -2147483648; public static int divide(int low,int high)
{
int value;
int lowValue;
int highValue;
int maxValue;
int mid; if (low > high)
return MIN_INT_UNM ;
if (low == high)
return s[low]; mid = (low + high)/2;
lowValue = divide(low,mid);
highValue = divide(mid + 1,high);
maxValue = lowValue < highValue ? highValue : lowValue;
for (int i = mid;i >= low;--i) {
value = s[i];
for (int j = mid + 1;j <= high;++j) {
value += s[j];
if (value > maxValue)
maxValue = value;
}
}
return maxValue;
} public static void main(String[] args)
{
int max = s[0];
int len = s.length - 1; max = divide(0,len); System.out.println(max);
}
}
给定一个数组,当中有正负数,求当中的一段“子数组”(即任意长度,连续的数字),使得这个“子数组”的和是所有“子数组”和中最大的, 如给定的数组为12, -8, 5, 66, -21, 0 ,35, -44,7,则最大的和的子数组为{12, -8, 5, 66, -21, 0 ,35},最大的和为89.
实现:分治法
语言:c 和 java
运行环境:BC和JDK
运行结果:在c下结果正确(结果55),但在java下(结果101)不正确
问题:这是为什么?
c code:
#include <stdio.h>#define MIN_INT_UNM -32768int s[] = {12,-8,5,66,-21,0,35,-44,7};int divide(int low,int high)
{
int value;
int lowValue;
int highValue;
int maxValue;
int mid;
int i,j; if (low > high)
return MIN_INT_UNM;
if (low == high)
return s[low]; mid = (low + high)/2;
lowValue = divide(low,mid);
highValue = divide(mid + 1,high);
maxValue = lowValue < highValue ? highValue : lowValue; for (i = mid;i >= low;--i) {
value = s[i];
for (j = i + 1;j <= high;++j) {
value += s[j];
if (value > maxValue)
maxValue = value;
}
} return maxValue;
}void main(void)
{
int max = s[0];
int len = sizeof(s) / sizeof(s[0]) - 1; max = divide(0,len); printf("%d\n",max);
}
java code:
public class Test2
{
static int s[] = {12,-8,5,66,-21,0,35,-44,7};
static final int MIN_INT_UNM = -2147483648; public static int divide(int low,int high)
{
int value;
int lowValue;
int highValue;
int maxValue;
int mid; if (low > high)
return MIN_INT_UNM ;
if (low == high)
return s[low]; mid = (low + high)/2;
lowValue = divide(low,mid);
highValue = divide(mid + 1,high);
maxValue = lowValue < highValue ? highValue : lowValue;
for (int i = mid;i >= low;--i) {
value = s[i];
for (int j = mid + 1;j <= high;++j) {
value += s[j];
if (value > maxValue)
maxValue = value;
}
}
return maxValue;
} public static void main(String[] args)
{
int max = s[0];
int len = s.length - 1; max = divide(0,len); System.out.println(max);
}
}
改为:for (int j = i + 1;j <= high;++j) {
结果就正确了
for (int j = i + 1;j <= high;++j) {