题意分析

  • 理解什么是子数组？
  • 要求子数组最大累加和
  • 注意题目对时间复杂度和空间复杂度的要求
    • 时间：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++ ){
            //累加求和