解题思路

  1. 使用 算法，维护两个变量：

    • ：记录全局最大和
    • ：记录当前位置结尾的最大和

  2. 对于每个位置 ，有两种选择：

    • 将当前数加入前面的子数组（）
    • 从当前数开始新的子数组（）

  3. 每次更新 后，更新

代码

#include <iostream>
#include <vector>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currSum = nums[0];
    
    for(int i = 1; i < nums.size(); i++) {
        currSum = max(nums[i], currSum + nums[i]);
        maxSum = max(maxSum, currSum);
    }
    
    return maxSum;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << maxSubArray(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currSum = nums[0];
        
        for(int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        
        return maxSum;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        System.out.println(maxSubArray(nums));
    }
}

def maxSubArray(nums):
    maxSum = nums[0]
    currSum = nums[0]
    
    for i in range(1, len(nums)):
        currSum = max(nums[i], currSum + nums[i])
        maxSum = max(maxSum, currSum)
    
    return maxSum

n = int(input())
nums = list(map(int, input().split()))
print(maxSubArray(nums))

算法及复杂度分析：

  • 算法: 算法， 算法
  • 时间复杂度：，只需要遍历一次数组
  • 空间复杂度：，只使用了常数额外空间