071子数组最大累加和问题与扩展下

题目一

package class071;

// 乘积最大子数组
// 给你一个整数数组 nums
// 请你找出数组中乘积最大的非空连续子数组
// 并返回该子数组所对应的乘积
// 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/
public class Code01_MaximumProductSubarray {

	// 这节课讲完之后，测试数据又增加了
	// 用int类型的变量会让中间结果溢出
	// 所以改成用double类型的变量
	// 思路是不变的
	public static int maxProduct(int[] nums) {
		double ans = nums[0], min = nums[0], max = nums[0], curmin, curmax;
		for (int i = 1; i < nums.length; i++) {
			curmin = Math.min(nums[i], Math.min(min * nums[i], max * nums[i]));
			curmax = Math.max(nums[i], Math.max(min * nums[i], max * nums[i]));
			min = curmin;
			max = curmax;
			ans = Math.max(ans, max);
		}
		return (int) ans;
	}

}

题目二

package class071;

// 子序列累加和必须被7整除的最大累加和
// 给定一个非负数组nums，
// 可以任意选择数字组成子序列，但是子序列的累加和必须被7整除
// 返回最大累加和
// 对数器验证
public class Code02_MaxSumDividedBy7 {
	// 正式方法
	// 时间复杂度O(n)
	public static int maxSum2(int[] nums) {
		int n = nums.length;
		// dp[i][j] : nums[0...i-1]
		// nums前i个数形成的子序列一定要做到，子序列累加和%7 == j
		// 这样的子序列最大累加和是多少
		// 注意 : dp[i][j] == -1代表不存在这样的子序列
		int[][] dp = new int[n + 1][7];
		dp[0][0] = 0;
		for (int j = 1; j < 7; j++) {
			dp[0][j] = -1;
		}
		for (int i = 1, x, cur, need; i <= n; i++) {
			x = nums[i - 1];
			cur = nums[i - 1] % 7;
			for (int j = 0; j < 7; j++) {
				dp[i][j] = dp[i - 1][j];
				// 这里求need是核心
				need = cur <= j ? (j - cur) : (j - cur + 7);
				// 或者如下这种写法也对
				// need = (7 + j - cur) % 7;
				if (dp[i - 1][need] != -1) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][need] + x);
				}
			}
		}
		return dp[n][0];
	}

	// 为了测试
	// 生成随机数组
	public static int[] randomArray(int n, int v) {
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			ans[i] = (int) (Math.random() * v);
		}
		return ans;
	}
	// 为了测试
	// 对数器
	public static void main(String[] args) {
		int n = 15;
		int v = 30;
		int testTime = 20000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int len = (int) (Math.random() * n) + 1;
			int[] nums = randomArray(len, v);
			int ans1 = maxSum1(nums);
			int ans2 = maxSum2(nums);
			if (ans1 != ans2) {
				System.out.println("出错了!");
			}
		}
		System.out.println("测试结束");
	}

}