题目
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
思考
前缀和也可以用来解决，但是相这种前缀和的值，求最大最小的时候我们完全可以使用动态方程的的方式解决
代码和注释
/**
使用动态规划五部曲
1.dp数组下标的含义
2.确定递推公式
3.初始化
4.遍历顺序
5.log验证
*/
public int maxSubArray(int[] nums) {
// 定义dp数组,dp下标表示每个子数组的和
int[] dp = new int[nums.length];
// 递推公式 dp[i] = Math.Max(dp[i-1] + nums[i], nums[i]);【包含当前值的最大值，加当前值的最大中】
// 初始化
dp[0] = nums[0];
// 最大值,最大存储位置
int max = nums[0];
// 遍历从前到后
for(int i = 1; i <= nums.length - 1; i++){
// 动态方程仅弄子数组和谁大
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
max = Math.max(max, dp[i]);
}
return max;
}
总结
以后这种前缀和的题，可以尝试使用动态规划来作。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96108.html
