面试题 16.17. 连续数列
https://leetcode.cn/problems/contiguous-sequence-lcci/
难度简单114
给定一个整数数组，找出总和最大的连续数列，并返回总和。
示例：
输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶：
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
方法一：简单dp
时间复杂度：O(n2)
空间复杂度：O(n)
内存挂了
class Solution {
public int maxSubArray(int[] nums) {
// 简单dp
// dp[i][j] 存储由i到j连续数列的和
if(nums.length==0) return -2147483648;
int n = nums.length;
int [][] dp = new int[n][n];
int ans = nums[0];
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(i==j) dp[i][i] = nums[i];
else dp[i][j]=dp[i][j-1]+nums[j];
ans = Math.max(ans,dp[i][j]);
}
}
return ans;
}
}
优化一下：
class Solution {
public int maxSubArray(int[] nums) {
// 简单dp
// dp[i][j] 存储由i到j连续数列的和
if(nums.length==0) return -2147483648;
int n = nums.length;
int [] dp = new int[n];
int ans = nums[0];
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(i==j) dp[j] = nums[i];
else dp[j]=dp[j-1]+nums[j];
ans = Math.max(ans,dp[j]);
}
}
return ans;
}
} 
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69045.html
