[size=x-large]题目：
一个整型数组里面存储的数据是正数，负数，零，求解数组中下标连续的一个片段使该片段的和是所有下标连续片段最大的？？？[/size]
[code="C#"]
public class IntArray
{
//这是整型数组类（IntArray）的数据成员 ，即一个整型数组
public int[] data;
//此类的构造函数法
public IntArray(int[] a)
{
data = a;
}
//打印数组，每十个一行
public void printArray()
{
int i = 0;
foreach (int j in data)
{
Console.Write(" " + j);
i++;
if (i % 10 == 0)
Console.WriteLine();
}
}
//用于返回数组中负数的个数
public int minusNumber()
{
int a = 0;
foreach (int i in data)
if (i < 0)
a++;
return a;
}
//整形数组的冒泡排序(采用大的沉底儿的方法)
public int[] bubbleSort()
{
int temp;
for (int i = 1; i < this.data.Length; i++)
for (int j = 0; j < this.data.Length - i; j++)
{
if (data[j] > data[j + 1])
{
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
return data;
}
//从数组中剔除一个指定值的元素 a，不管它的重数有几次 ，返回剔除后的新数组（比原来少一个元素）
public int[] ridOneElement(int a)
{
bool flag = false;
int j = 0;
int[] tempArray = new int[this.data.Length - 1];
foreach (int i in data)
{
if (i != a || flag)
{
tempArray[j] = i;
j++;
}
if (i == a)
flag = true;
}
return tempArray;
}
//此方法用于返回 当前 元素之后（包括当前）的第一个 正 元素 的 索引值，若 不存在则返回 -1
public int nextPositiveIndex(int currentIndex)
{
for (int i = currentIndex; i < this.data.Length; i++)
if (data[i] > 0)
return i;
return -1;
}
//此方法用于返回 当前 元素之后（包括当前）的第一个 负 元素 的 索引值，若 不存在则返回 -1
public int nextMinusIndex(int currentIndex)
{
for (int i = currentIndex; i < this.data.Length; i++)
if (data[i] < 0)
return i;
return -1;
}
//求一段连续元素的和 ，即两个索引之间（包括端点）的元素的和
public int sessionSum(int start, int end)
{
int sum = 0;
for(int i=start;i<=end;i++)
sum=sum+data[i];
return sum;
}
//给定一个整数数组,从中切出一个连续片段,保证其元素和最大
public ArraySession sliceMax()
{
int dataLength = this.data.Length;//缓存数组长度
//判断是不是数组内没有正整数，如果没有返回最大的非正数
int flag = 0;
for (int i = 0; i < dataLength; ++i)
{
if (data[i] > 0)
break;
++flag;
}
if (flag == dataLength)
{
int max1 = data[0], index = 0;
for (int i = 0; i < dataLength; ++i)
{
if (data[i] >= max1)
{
max1 = data[i];
index = i;
}
}
return new ArraySession(index, index, max1);//全为非正数时，一定从这一局返回。
}
//下面是对数组内有正整数的情况考虑的
List<ArraySession> node = new List<ArraySession>();
for (int start = 0; start < dataLength; start++)
{
if (data[start] <= 0 || start != 0 && data[start - 1] > 0)
continue;//起始点是非正数的或者前一个数是正数的，肯定不是最大序列，继续下一轮
for (int end = start; end < dataLength; end++)
{
if (data[end] <= 0 || end < dataLength -1 && data[end + 1] > 0)//先判断这个数是否为非正，再看下一个是否为正
continue;//终止点是非正数的或者 下一个点是正数的，肯定不是最大序列，继续下一轮
int sum = 0;
for (int k = start; k <= end; k++)
{
sum = sum + data[k];
}
node.Add(new ArraySession(start, end, sum));
}
}
int max2 = node[0].sum;
ArraySession result=new ArraySession(0,0,0);//结构不可赋值为null关键字
foreach (ArraySession i in node)
{
if (max2 <= i.sum)//此处的等于很重要
{
max2 = i.sum;
result = i;
}
}
return result;
}
}
//////////////////////////////////
public class ArraySession
{
public int start;
public int end;
public int sum;
//构造函数
public ArraySession(int start, int end, int sum)
{
this.start = start;
this.end = end;
this.sum = sum;
}
//打印此段的基本信息
public void sessionPrint()
{
Console.WriteLine("此段的开端索引值为"+start);
Console.WriteLine("此段的结尾索引值为"+end);
Console.WriteLine("此段的元素之和为"+sum);
}
}
////////////////////////////////
class MainClass
{
//主函数 ，程序的入口点 ，此类主要用作调试函数
static void Main(string[] args)
{
//int[] array = new int[10] { -1, -2, -1, -2, -3, -4, -5, -6,-7, -8 };
//new IntArray(new Mathlet().arrayMultiMax(array)).printArray();
//Console.WriteLine(new Mathlet().triFibonacci(BasicFunctions.intInput("请输入一个整数")));
//Console.ReadKey();
//new ArraySession(1, 2, 3).sessionPrint();
int[] array = new int[10] { 1, 2, -1, 2, -3, 4, -2, 6, -7, -8 };
new IntArray(array).sliceMax().sessionPrint();
Console.ReadKey();
}
}
[/code]
变成Java代码，只需改个别地方，这是我以前写过的一个问题。
我觉得应该先把0和小于0的数字替换成非字符，然后把这个数组拼成一个字符串，然后用regx截断。。。然后再计算个片段（要保存该片段原始位置）的值，求出最大的一个片段。。就好了吧。。。 :)
[code="java"]public static void main(String[] args) {
// TODO Auto-generated method stub
int[] dataSource = new int[] { 1, -1, 3, 4, 5, 6, 0, 9, -3, 8, 3, 2,
34, 3, 2, -3, 9 };
String a = "a";// 用于替换小于等于0的数字
String s = replaceAllLeZero(dataSource, a);
String[] ss = s.split(",a,");
String maxS = maxString(ss);
String[] maxss = maxS.split(",");
for (String ms : maxss)
System.out.print(ms+",");
}
private static String maxString(String[] ss) {
// TODO Auto-generated method stub
String maxS = null;
int sum = 0;
int index = 0;
int cc = 0;
for(int i=0;i<ss.length;i++){
cc = cacl(ss[i]);
if(cc >= sum){
sum = cc;
index = i;
}
}
return ss[index];
}
private static int cacl(String str) {
// TODO Auto-generated method stub
String[] ss = str.split(",");
int sum = 0;
for(String s : ss){
sum += Integer.valueOf(s);
}
return sum;
}
private static String replaceAllLeZero(int[] dataSource, String replacer) {
// TODO Auto-generated method stub
StringBuilder sb = new StringBuilder();
for (int i : dataSource) {
if (i <= 0)
sb.append(replacer);
else
sb.append(i);
sb.append(",");
}
int index = sb.lastIndexOf(",");
if (index != -1)
sb.deleteCharAt(index);
return sb.toString();
}[/code]
偶错了-。-没看清题目-。- 8)