牛客-NC19-子数组的最大累加和问题

方法一：直接遍历法（最优解）

思路：这里注意题目对时间、空间复杂度的要求，所以我们不能使用动态规划来写（虽然后面提交了也没有超时）。我们首先默认数组中的第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), 未使用额外的空间。