网站建设会碰到什么问题,企业简介怎么写,videopro wordpress,怎样用flash做游戏下载网站题目#xff1a; 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组是数组中的一个连续部分。
解题思路#xff1a; 方法一#xff1a;看到子数组和#xff0c;首…题目 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组是数组中的一个连续部分。
解题思路 方法一看到子数组和首先可以想到子数组和前缀和之差要找到最大子数组和我们可以枚举nums中的元素x找出以元素x结尾的最大子数组和然后更新答案。
要寻找以元素x结尾的最大子数组和我们只需要知道x元素之前的最小子数组和。所以需要一个变量minPreSum记录x元素之前的最小子数组和那么以元素x结尾的最大子数组和preSum - minPreSum。
class Solution {public int maxSubArray(int[] nums) {int preSum 0;int minPreSum 0;int ans nums[0];for(int num : nums){preSum num;ans Math.max(ans, preSum - minPreSum);minPreSum Math.min(minPreSum, preSum);}return ans;}
}方法二动态规划。要知道以x结尾的最大子数组和我们可以通过以x-1结尾的最大子数组和推导出来。状态转移方程为dp[i] max(dp[i-1] nums[i], nums[i])dp[i]表示以i结尾的最大子数组和在枚举i的过程中更新答案。
class Solution {public int maxSubArray(int[] nums) {int n nums.length;int[] dp new int[n];dp[0] nums[0];int ans dp[0];for(int i 1; i n; i){dp[i] Math.max(dp[i-1] nums[i], nums[i]);ans Math.max(dp[i], ans);}return ans;}
}优化 因为在计算dp[i]的过程中只会用到dp[i-1]所以我们可以用一个变量来代替。
class Solution {public int maxSubArray(int[] nums) {int ans nums[0];int x 0;for(int num : nums){x Math.max(x num, num);ans Math.max(x, ans);}return ans;}
}
