深圳市建设网站公司,网站排名优化手机,企业网站pv是什么,dedecms学校网站解题思路#xff1a;
1.先把数组为空和数组的长度为1时的特殊情况分别开来。声明一个sum变量用于计算数组中的连续子数组的总和值 。在声明一个guo变量用于一种接收sum中的前i-1的总和。另一种接收sum中前i的总和#xff0c;主要根据sum的值来判断是接收的哪一种。在声明一个…解题思路
1.先把数组为空和数组的长度为1时的特殊情况分别开来。声明一个sum变量用于计算数组中的连续子数组的总和值 。在声明一个guo变量用于一种接收sum中的前i-1的总和。另一种接收sum中前i的总和主要根据sum的值来判断是接收的哪一种。在声明一个guo变量用于接收最大和的连续子数组的值。
2.在遍历过程中要把sum分情况来进行赋值和更新。如果当前i-1的sum值小于o为负数时就抛弃前i-1的sum值把nums【i】的值复制给sum。如果当前i-1的sum值大于0我们就要更新sum值来判断是前i-1的sum值大还是前i的sum值大。之后再来更新连续最大和。我写这题时我敢觉的思路有点抽向和奇特一股脑的写下去所以我不知道这个解法属于哪一类算法。
class Solution {public int maxSubArray(int[] nums) {//数组为空时if(nums.length1){return 0;}//数组的长度为1时if(nums.length1){return nums[0];}//计算数组中的连续子数组的总和值int sumnums[0];//一种接收sum中的前i-1的总和。另一种接收sum中前i的总和。主要根据sum的值来判断是接收的哪一种。int guo0;//接收最大和的连续子数组的值int maxnums[0];for(int i1;inums.length;i){//把前i-1的sum值赋值给guoguosum;//判断前i-1的sum值小于o为负数时就抛弃前i-1的sum值if(sum0){//把nums【i】的值复制给sumsumnums[i];//来更新连续最大和maxMath.max(max,sum);continue;}//如果前i-1的sum值大于0我们就要更新sum值来判断是前i-1的sum值大还是前i的sum值大sumnums[i];//判断是前i-1的sum值大还是前i的sum值大。括号中的guo为前i-1的zum值guoMath.max(guo,sum);//来更新连续最大和maxMath.max(max,guo);}return max;}
}
动态规划解法
1.先把数组为空和数组的长度为1时的特殊情况分别开来之后声明一个dp数组表示下标为i时的连续最大和初始化dp数组的值为nums[0]递推公式为dp[i]Math.max(dp[i-1]nums[i],nums[i])
判断是前i的dp数组值大还是当前nums[i]的值大赋值给dp数组dp[i]。最后来更新连续最大和
class Solution {public int maxSubArray(int[] nums) {//数组为空时if(nums.length1){return 0;}//数组的长度为1时if(nums.length1){return nums[0];}//声明dp数组dp数组表示下标为i时的连续最大和int dp[]new int [nums.length];//初始化dp数组dp[0]nums[0];//接受最大和值int maxnums[0];//for循环遍历来进行推导后面的dp数组的值for(int i1;inums.length;i){//递推公式dp[i]Math.max(dp[i-1]nums[i],nums[i]);//判断最大值和对比最大值maxMath.max(dp[i],max);}return max;}
}
