去一家公司面试,面试我的前辈给出的一个算法题
题目是这样的:
? ? 有一个数组,其中的元素有负数正数和0,在其中截取连续的片段形成子数组,求子数组元素之和最大的子数组。
?
当时只想到了穷举法,前辈给指点了一种方法,当时手写了个大概,回来之后敲出来了
今天收到了offer,顺便把代码记录下来
class="java">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
?