数据结构和算法面试题：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

阳光穿透心脏的1/2处 2024-03-16 17:05 27阅读 0赞

## 数据结构和算法面试题：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 ##

简介：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

该算法的实现思路如下：

1.  使用一个变量`ans`存储最终的答案，使用一个变量`cur`存储当前的连续子数组和。
2.  遍历整个数组，对于每一个数字，更新`cur`为它自身和`(cur + nums[i])`之间的较大值。如果`cur`大于`ans`，则将`ans`更新为`cur`。
3.  遍历完数组后，返回`ans`作为最大子数组和。

下面是使用C++实现查找最大子数组和的代码，并附带详细注释：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0]; // 初始化最终答案
        int cur = nums[0]; // 初始化当前连续子数组
    
        for (int i = 1; i < nums.size(); ++i) {
            cur = max(nums[i], cur + nums[i]); // 更新当前连续子数组和
            ans = max(ans, cur); // 更新最终答案
        }
    
        return ans;
    }
    
    int main() {
        vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int ans = maxSubArray(nums);
        cout << ans << endl; // 6
        return 0;
    }

该算法遍历整个数组，维护了两个变量`ans`和`cur`，其中`ans`表示目前找到的最优连续子序列的和，`cur`是num\[i\]为结尾的连续子数组的和。在每次遍历中，用当前数值num\[i\]与num\[i\]+cur之间的较大值更新cur并求出当前子数组msum\[i\]的和，将其与ans作比较，并记录在ans中；最终返回ans作为答案。由于只有一层循环，该算法的时间复杂度为 O(n)。

*  java版本

import java.util.Arrays;
    
    public class Main {
        
        public static int maxSubArray(int[] nums) {
        
            int ans = nums[0]; // 初始化最终答案
            int cur = nums[0]; // 初始化当前连续子数组
    
            for (int i = 1; i < nums.length; ++i) {
        
                cur = Math.max(nums[i], cur + nums[i]); // 更新当前连续子数组和
                ans = Math.max(ans, cur); // 更新最终答案
            }
    
            return ans;
        }
    
        public static void main(String[] args) {
        
            int[] nums = {
        -2, 1, -3, 4, -1, 2, 1, -5, 4};
            int ans = maxSubArray(nums);
            System.out.println(ans); // 6
        }
    }