最大和子数组
2018-07-17 本文已影响0人
shoulda
题目:
给定一个数组arr, 返回所有子数组的累加和中, 最大的累加和
package basic_class_08;
public class Code_02_SubArrayMaxSum {
public static int maxSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i != arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
public static void printArray(int[] arr) {
for (int i = 0; i != arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] arr1 = { -2, -3, -5, 40, -10, -10, 100, 1 };
System.out.println(maxSum(arr1));
int[] arr2 = { -2, -3, -5, 0, 1, 2, -1 };
System.out.println(maxSum(arr2));
int[] arr3 = { -2, -3, -5, -1 };
System.out.println(maxSum(arr3));
}
}