解题思路

这是一道经典的动态规划问题，也可以用贪心算法解决。主要思路如下：

  1. 维护两个变量：

    • : 当前连续子数组的和
    • : 已找到的最大连续子数组和

  2. 遍历数组时：

    • 累加当前元素到
    • 如果 ，重置 （放弃之前的子数组）
    • 如果 ，更新

  3. 特殊情况：

    • 如果所有数都是负数，返回最大的负数
    • 初始化 来处理全负数的情况

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int sum = -1, temp = 0;
    
    for(int i = 0; i < N; i++) {
        int num;
        cin >> num;
        temp += num;
        
        // 如果当前和为负，放弃之前的子数组
        if(temp < 0) {
            temp = 0;
        }
        else {
            sum = max(sum, temp);
        }
    }
    
    cout << sum << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int sum = -1, temp = 0;
        
        for(int i = 0; i < N; i++) {
            int num = sc.nextInt();
            temp += num;
            
            if(temp < 0) {
                temp = 0;
            }
            else {
                sum = Math.max(sum, temp);
            }
        }
        
        System.out.println(sum);
    }
}

n = int(input())

sum_max = -1
temp = 0

for _ in range(n):
    num = int(input())
    temp += num
    
    if temp < 0:
        temp = 0
    else:
        sum_max = max(sum_max, temp)

print(sum_max)

算法及复杂度

  • 算法：动态规划/贪心
  • 时间复杂度： - 只需要遍历一次数组
  • 空间复杂度： - 只需要两个变量存储状态