Maximum contiguous subarray sum (最大连续子数组和)
发布时间
阅读量：
阅读量
对于一个整数序列 nums ，需要确定其中连续子序列（至少包含一个元素）的和最大值，并将该最大和作为结果返回。
示例:
**输入:****输出:****解释:**- 思路：首先将dp[0]初始化为nums[0]，随后对于每个i，dp[i]的值取max{dp[i] + nums[i], nums[i]}，最终取dp数组中的最大值即为所求结果。然而，为了进一步减少空间占用，可以采用空间复杂度为O(1)的优化方法。
时间复杂度为O(N)，空间复杂度为O(1)的解法：通过变量maxsum来记录以nums[i]作为结尾的最大子序列和，并在过程中持续更新全局最大子序列和ans的值。
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int maxsum = nums[0];
for(int i = 1; i < nums.size(); i++){
maxsum = maxsum + nums[i] > nums[i] ? maxsum + nums[i] : nums[i];
ans = maxsum > ans ? max全部评论 (0)
还没有任何评论哟~