Class Code05_MaxSubArraySum

src/videocode/Code05_MaxSubArraySum.java:3–90

package videocode;

public class Code05_MaxSubArraySum {

	public static int maxSubArraySum1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		int ans = Integer.MIN_VALUE;
		for (int L = 0; L < N; L++) {
			for (int R = L; R < N; R++) {
				// arr[L..R]
				int sum = 0;
				for (int i = L; i <= R; i++) {
					sum += arr[i];
				}
				ans = Math.max(ans, sum);
			}
		}
		return ans;
	}

	public static int maxSubArraySum2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		// dp[i] : 子数组必须以arr[i]结尾的时候，子数组的最大累加和是多少？
		int[] dp = new int[N];
		dp[0] = arr[0]; // 0..0
		int ans = arr[0];
		// dp[1] -> dp[0]
		// dp[2] -> dp[1]
		// dp[3] -> dp[2]
		// dp[4] -> dp[3]
		// dp[i] => dp[i-1]
		for (int i = 1; i < N; i++) {
			dp[i] = Math.max(arr[i], arr[i] + dp[i - 1]);
			ans = Math.max(ans, dp[i]);
		}
		return ans;
	}

	public static int maxSubArraySum3(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int N = arr.length;
		// pre -> dp[0]
		int pre = arr[0];
		int ans = arr[0];
		for (int i = 1; i < N; i++) {
		//  dp[3]                           dp[2]
			pre = Math.max(arr[i], arr[i] + pre);
			ans = Math.max(ans, pre);
		}
		return ans;
	}