Java算法--第四章--多维数组和矩阵（5）题目：子数组最大累加和

Java算法–第四章–多维数组和矩阵（5）题目：子数组最大累加和

给定一个数组arr，返回子数组的最大累加和
例:arr=[1,-2,3,5,-2,6,-1];所有的子数组中[3,5,-2,6]可以累加出最大的和12，所以返回12

代码：

package matrix;

public class MaxSumArray {

	public static void main(String[] args) {
		int[] arr = { 1, -2, 3, 5, -2, 6, -1 };
		int max = findByDp(arr);

	}

	// 暴力破解O（n²）
	static void findBuForce(int[] arr) {
		int maxSum = arr[0];

		for (int i = 0; i < arr.length; i++) {
			int sum = arr[i];// 某个元素为子数组的第一个元素
			int maxOf = sum;
			for (int j = i + 1; i < arr.length; j++) {
				sum += arr[j];// 累加后续数组元素
				if (sum > maxOf) {
					maxOf = sum;
				}
			}
			if (maxOf > maxSum) {
				maxSum = maxOf;
			}
		}
		System.out.println(maxSum);
	}

	// 递推法O（n）
	static int findByDp(int[] arr) {
		int sum = arr[0];
		int max = sum;
		int left = 0, right = 0;
		for (int i = 1; i < arr.length; i++) {
			if (sum >= 0) {
				sum += arr[i];
			} else {
				sum = arr[i];
				left = i;
			}
			if (sum > max) {
				max = sum;
				right = i;
			}
		}
		System.out.println(max + ",left = " + left + ",right = " + right);
		return max;
	}
}

输出：

12,left = 2,right = 5