题解

解题思路

1. 计算整个数组的总和
2. 计算数组中的最大子数组和（使用Kadane算法）
3. 将这两个值相加作为最终结果

实现步骤

1. 读取输入：处理多个测试用例，直到遇到$N=0$为止
2. 计算总和：遍历数组计算所有元素的和
3. 计算最大子数组和：使用Kadane算法找到连续子数组的最大和
4. 输出结果：将数组总和与最大子数组和相加后输出

复杂度分析

1. 时间复杂度：$O(N)$
   • 计算总和需要$O(N)$时间
   • Kadane算法需要$O(N)$时间
   • 总体时间复杂度为线性
2. 空间复杂度：$O(1)$
   • 只使用了常数级别的额外空间

C++代码

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// 计算最大子数组和的函数（Kadane算法）
int maxSubarraySum(const vector<int>& nums) {
    int max_current = nums[0];  // 当前子数组的最大和
    int max_global = nums[0];   // 全局最大子数组和
    
    // 遍历数组中的每个元素
    for (int i = 1; i < nums.size(); ++i) {
        // 决定是开始新的子数组还是扩展当前子数组
        max_current = max(nums[i], max_current + nums[i]);
        // 更新全局最大值
        max_global = max(max_global, max_current);
    }
    
    return max_global;
}

// 解决问题的核心函数
int solve(const vector<int>& nums) {
    int total_sum = 0;  // 数组所有元素的总和
    
    // 计算数组总和
    for (int num : nums) {
        total_sum += num;
    }
    
    // 计算最大子数组和
    int max_subarray = maxSubarraySum(nums);
    
    // 返回总和与最大子数组和的和
    return total_sum + max_subarray;
}

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(0);                  // 解除cin和cout的绑定
    
    int N;  // 每个测试用例的数字个数
    
    // 处理多个测试用例，直到N=0
    while (cin >> N && N != 0) {
        vector<int> nums(N);  // 存储输入的数字
        
        // 读取N个数字
        for (int i = 0; i < N; ++i) {
            cin >> nums[i];
        }
        
        // 计算并输出结果
        cout << solve(nums) << "\n";
    }
    
    return 0;
}