一个面试题

去一家公司面试，面试我的前辈给出的一个算法题

题目是这样的：

    有一个数组，其中的元素有负数正数和0，在其中截取连续的片段形成子数组，求子数组元素之和最大的子数组。

 

当时只想到了穷举法，前辈给指点了一种方法，当时手写了个大概，回来之后敲出来了

今天收到了offer，顺便把代码记录下来

package org.quainter.AlgorithmTest;

public class ArraySplitTest {
	public static void main(String[] args) {
		
		int arr[] = {-20, 26, 5, 0, 54, 2, 566, -32, -4, 0, 546, -12, 13};
		
		int sum = 0;
		int start = 0;
		int end = 0;
	
		for(int i=0; i<arr.length; i++) {
			int temp_sum = 0;
			for(int j=i; j<arr.length; j++) {
				
				temp_sum += arr[j];
				if(temp_sum > sum) {
					sum = temp_sum;
					start = i;
					end = j;
				}
			}
		}
		System.out.println("start-->下标:"+ start +"\nend-->下标:"+ end);
	}
}

 

结果是：

start-->下标:1
end-->下标:12