牛客-NC19-子数组的最大累加和问题
NC19. 子数组的最大累加和问题（easy）
方法一：直接遍历法（最优解）
思路：这里注意题目对时间、空间复杂度的要求，所以我们不能使用动态规划来写（虽然后面提交了也没有超时）。我们首先默认数组中的第0个元素是最大的，然后从下标1开始，遵循以下规则：（1）保证每个位置的值至少比原始的大；（2）每次遍历都更新ret，用于保存当前最大的累加和。于是，可以写出以下代码：
import java.util.*;
public class Solution {
/** * max sum of the subarray * @param arr int整型一维数组 the array * @return int整型 */
public int maxsumofSubarray (int[] arr) {
// write code here
// 特判
if (arr == null || arr.length == 0) return 0;
if (arr.length == 1) return arr[0];
// 直接遍历法
int ret = arr[0];
for (int i = 1; i < arr.length; i++) {
// 保证每个位置的值至少比原始的大
arr[i] = Math.max(arr[i], arr[i - 1] + arr[i]);
// 每次遍历都更新ret，用于保存当前最大的累加和。
ret = Math.max(arr[i], ret);
}
// 返回该值
return ret;
}
}
时间复杂度： O(N)，最坏情况下，需要遍历所有数组元素，即子数组为整个数组。
空间复杂度： O(1), 未使用额外的空间。
查看6道真题和解析