一个道说难不难，说简单不简单的Java编程题

这种贴也可以上首页？javaEye现在是疯了

大致思路：
对数列元素逐个求和，和值大于0的部分作为一段（也就是一旦出现和值小于等于0则另起一段，因为这时该位置前面的部分对后续求和没有任何贡献了）。找出峰值最高的一段，从该段起始位置到该段峰值位置即为解。如果所有值都小于等于0，则数列中的最大值为解。

伪代码：

int sectionStart = 0;
int start = 0;
int end = -1;
int sum = 0;
int max = 0;
int maxNum = Integer.MINVALUE


for (int i = 0; i < a.length; i++) {
    if (a[i] > maxNum) maxNum = a[i];
    sum += a[i];
    if (sum > max) {
        max = sum;
        end = i;
        start = sectionStart;
    } else if (sum <= 0) {
        sectionStart = i + 1;
        sum = 0;
    }
}

//output
if (end < 0) {
   System.out.println("Max value:" + maxNum);
   System.out.println("Sublist: {" + maxNum + "}");
} else {
   System.out.println("Max value:" + sum);
   System.out.print("Sublist: {" + a[start]);
   for (int i = start + 1; i <= end; i++) {
     System.out.print("," + a[i]);
   }
   System.out.println("}");
}

随手打的，没实际运行过。

思路不错，如果全是负数会怎么样?
可以考虑把max初始值赋为第一个元素

var arr = [1,2,0,5,4,12,0,-1,-2,4,8,12,0]; 
arr = arr.toString().replace(/(,?-\d+,)+/g,'|').replace(/,/g,'+').split('|').sort(function(a,b){return eval(b)-eval(a);});
function output (s){
    var arr = s.split('+');
    console.log(arr.join(','));
    if(arr.pop()== 0 ){
       output(arr.join('+'));     
    }
}
for(var i = 0 ; i<arr.length  ; i++){
    output(arr[i]);
    if(eval(arr[i])!=eval(arr[i+1])){
        break;
    }
}

 贴个js的~

全是负数或零的话最大子集肯定只有一个元素，会进end < 0的分支。因为是直接手写的程序，安全起见用了一个额外的变量maxNum来记录最大元素值。如果能调试的话，是可以合并到max里的。

如果仅仅是求和的话，私以为仅将大于零的数字集合为一组就可以了。
如果全都小于零，只取出最大的那个数就可以了。

+1

maxsofar = 0
maxendinghere = 0

for i = [0,n)
	maxendinghere = max(maxendinghere + x[i],0)
	maxsofar = max(maxsofar,maxendinghere)

咋一看简单，
仔细一想，确实有点难度，
再一想，也不过尔尔

public class biggestOfSubArr {
	static int findMax(int[] arr) {
		int max = 0;
		int temp = 0;
		for (int i = 0; i < arr.length; i++) {
			temp = 0;
			for (int j = i; j < arr.length; j++) {
				temp += arr[j];
				System.out.print("arr" + i + "," + j + " :[");
				for (int count = i; count <= j; count++) {
					System.out.print(arr[count] + ",");
				}
				System.out.println("]  result: " + temp);
				if (temp > max) {
					max = temp;
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		int arr[] = { 1, 2, 0, 5, -1, -2, 4, 8, 12 };
		System.out.print(findMax(arr));
	}
}