青岛企业网站建设,国外做水广告网站大全,宜昌微网站建设,软件界面设计欣赏题目描述 给定一个整数数组和一个整数 k#xff0c;找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。 返回最大的和。 注意事项 子数组最少包含一个数 样例 给出数组 [-1,4,-2,3,-2,3] 以及 k 2#xff0c;返回 8 思路 dp[i][j] max(… 题目描述 给定一个整数数组和一个整数 k找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。 返回最大的和。 注意事项 子数组最少包含一个数 样例 给出数组 [-1,4,-2,3,-2,3] 以及 k 2返回 8 思路 dp[i][j] max(dp[x][j-1]maxs[x1][i]) dp[i][j] 表示前 i 个数中 j 个子数组的最大值 maxs[i][j] 表示 第i个数到第j个数中最大子数组的和。 代码 public class Solution {/*** param nums: A list of integers* param k: An integer denote to find k non-overlapping subarrays* return: An integer denote the sum of max k non-overlapping subarrays*/public int maxSubArray(int[] nums, int k) {// write your code hereint[][] maxs new int[nums.length][nums.length];int[][] dp new int[nums.length][k1];for(int i0; inums.length; i) {for(int ji; jnums.length; j) {maxs[i][j] maxSum(nums, i, j);}}for(int i0; idp.length; i) {for(int j0; jdp[i].length; j) {dp[i][j] Integer.MIN_VALUE;}}for(int i0; idp.length; i) {dp[i][1] maxs[0][i];}for(int i1; inums.length; i) {for(int j2; jk; j) {for(int xj-2; xi; x) {dp[i][j] Math.max(dp[i][j], dp[x][j-1] maxs[x1][i]);}}}return dp[nums.length-1][k];}private int maxSum(int[] nums, int i, int j) {int sum 0, maxs Integer.MIN_VALUE;for(int x i; x j; x) {sum nums[x];if (maxs sum) {maxs sum;}if (sum 0) {sum 0;}}return maxs;}}转载于:https://www.cnblogs.com/hujunzheng/p/7376237.html
