数据结构和算法面试题：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
简介：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
该算法的实现思路如下：
- 使用一个变量
ans存储最终的答案，使用一个变量cur存储当前的连续子数组和。 - 遍历整个数组，对于每一个数字，更新
cur为它自身和(cur + nums[i])之间的较大值。如果cur大于ans，则将ans更新为cur。 - 遍历完数组后，返回
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 } }
