这道题是经典的“最大子数组和”问题，可以使用 Kadane 算法解决。Kadane 算法的核心思想是遍历数组时，通过维护一个当前子数组和 current_sum 和一个全局最大子数组和 max_sum 来实现。具体步骤如下：
- 初始化两个变量：
current_sum为 0，max_sum为负无穷大（或数组的第一个元素）。 - 遍历数组中的每个元素
x：- 将
x加到current_sum上。 - 如果
current_sum大于max_sum，更新max_sum。 - 如果
current_sum小于 0，则将current_sum置为 0，因为负的和只会降低之后的和。
- 将
- 返回
max_sum。
这个算法的时间复杂度为 O(n)，因为我们只需要遍历数组一次。
public class MaxSubarraySum {
/**
* 计算给定销售额数组的最大连续子数组和
* @param sales 销售额数组
* @return 最大连续子数组和
*/
public static int maxSubArray(int[] sales) {
// 当前子数组和
int currentSum = 0;
// 全局最大子数组和，初始化为最小的整数值
int maxSum = Integer.MIN_VALUE;
// 遍历数组中的每个元素
for (int x : sales) {
// 将当前元素加到当前子数组和中
currentSum += x;
// 如果当前子数组和大于全局最大子数组和，则更新全局最大子数组和
if (currentSum > maxSum) {
maxSum = currentSum;
}
// 如果当前子数组和小于0，则将当前子数组和重置为0
if (currentSum < 0) {
currentSum = 0;
}
}
// 返回全局最大子数组和
return maxSum;
}
public static void main(String[] args) {
// 示例1：测试用例
int[] sales1 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
// 示例2：测试用例
int[] sales2 = {5, 4, -1, 7, 8};
// 输出示例1的结果，期望输出: 6
System.out.println(maxSubArray(sales1));
// 输出示例2的结果，期望输出: 23
System.out.println(maxSubArray(sales2));
}
}
代码注释说明：
- 函数注释：
maxSubArray函数：计算给定销售额数组的最大连续子数组和。- 参数
sales：销售额数组。 - 返回值：最大连续子数组和。
- 变量初始化：
currentSum：当前子数组的和，初始值为0。maxSum：全局最大子数组的和，初始值为最小的整数值Integer.MIN_VALUE。
- 遍历数组：
- 使用增强的
for循环遍历数组sales中的每个元素x。 - 将当前元素
x加到currentSum中。 - 如果
currentSum大于maxSum，则更新maxSum。 - 如果
currentSum小于0，则将currentSum重置为0，以避免负数和降低后续子数组的和。
- 使用增强的
- 返回结果：
- 返回
maxSum，即最大连续子数组的和。
- 返回
- 示例测试：
- 定义两个测试用例
sales1和sales2。 - 打印
sales1和sales2的最大子数组和，期望输出分别为6和23。
- 定义两个测试用例