题解 | 子数组的最大累加和问题

题意分析

• 理解什么是子数组？
• 要求子数组最大累加和
• 注意题目对时间复杂度和空间复杂度的要求
  • 时间：O（N）
  • 空间：O（1）
• 注意备注信息：包含了所给数据的边界范围，这对算法的选择至关重要的。

解法一：暴力解

思路步骤：

• 常规思路，直接两层for循环暴力枚举
• 找到符合题意的最大累加和
• 虽然理论上可行，但是时间复杂度为O(N^2)，实际运行是无法AC的。仅仅作为一种学习思路。

C++参考代码：(超时)

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
          int result = INT32_MIN;
        int count = 0;
        for (int i = 0; i < arr.size(); i++) { // 设置起始位置
            count = 0;
            for (int j = i; j < arr.size(); j++) { // 每次从起始位置i开始遍历寻找最大值
                count += arr[j];
                result = count > result ? count : result;
            }
        }
        return result;

    }
};

复杂度分析：

时间复杂度：O(N^2) N为数组长度，俩层循环，，根据大O一般法则可知复杂度O(N^2)

空间复杂度：O(1) 常数空间

解法二：贪心

思路步骤：

• 怎么贪？

• 不妨以case:[1, -2, 3, 5, -2, 6, -1]为例

• 当遇到-2时，累加和反而变为负数，此种情况不可能成为最大和

• 因此在遇到负数时，因该重置累加和为0，继续从i+1开始计算

• 最后得到一个局部最大和

• 最终得到一个全局最大和，即是答案

• 请参考图解
  

  Java参考代码：

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
        //存放临时答案
        int thisSum=0;
        //存放最终答案，注意初始化的值
        int ans = Integer.MIN_VALUE;
        int len = arr.length;
        for(int i=0;i<len;i++ ){
            //累加求和
            thisSum