算法-最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

方式一：暴力解法

public class _53_最大子序和 {
    public static void main(String[] args) {
        int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));
    }

    //暴力法
    //暴力解法的思路，第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值
    public static int maxSubArray(int[] nums) {
        int max = 0;
        int temp = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < nums.length; i++) {
            temp = 0;
            for (int j = i; j < nums.length; j++) {
                temp += nums[j];
                //如果当前的相加<max,那么久已经是具有最大和的连续子数组
                if (temp > max) {
                    max = temp;
                    left = i;
                    right = j;
                }
            }
        }
        System.out.println("具有最大和的连续子数组起始位置：left:" + left + " right :" + right);
        return max;
    }
}

输出:

具有最大和的连续子数组起始位置：left:3 right :6
6

复杂度分析

两个for循序 ：

• 时间复杂度O(n^2)
• 空间复杂度O(1)

---

---

---

方式二：贪心解法

//贪心解法，如何省掉一层for循环呢
//贪心贪的是哪里呢？
//如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
//同样的道理，遍历nums，从头开始用count累积，这里需要理清楚题意，具有最大和的连续子数组，返回其最大和。
//只要从头开始用count累积，用一个result记录当前累计最大的数， 只要count的累积不为负数。
//因为如果累计到为负数，就假定为-1，那么下一个i+1的元素相加 -1， 肯定得到的要i+1的元素小，所以还不如直接从i+1的元素开始
//那么就是可以理解为result是最大的和。

public static int maxSubArray2(int[] nums) {
  int result = 0;
  int count = 0;
  for (int i = 0; i < nums.length; i++) {
    count += nums[i];
    if (count > result) { 
      result = count;
    }
    if (count <= 0) 
      count = 0; 
    }
    return result;
}

复杂度分析

一个for循序 ：

• 时间复杂度O(n)
• 空间复杂度O(1)

---

---

---

方式三：动态规划解法

• dp[i]表示nums中以nums[i]结尾的最大自序和
• dp[i] = max(dp[i] = dp[i - 1] + nums[i] , dp[i] = nums[i]), 也就是跟贪心算法一样
• dp[i]是当前数字，要么是与前面的最大子序的和

public static int maxSubArray3(int[] nums) {
  //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
  int result = Integer.MIN_VALUE;
  int numsSize = nums.length;
  int dp[] = new int[numsSize];//dp[i]表示nums中以nums[i]结尾的最大子序和
  //如果数组只有一个元素
  if (numsSize == 1) {
    return nums[0];
  }
  dp[0] = nums[0];
  result = dp[0];
  for (int i = 1; i < numsSize; i++) {
  // 跟贪心算法一样，如果因为如果累计到为负数，就假定为-1，那么下一个i+1的元素相加 -1， 肯定得到的要i+1的元素小，所以还不如直接从i+1的元素开始
    if (dp[i - 1] + nums[i] > nums[i]) {
      dp[i] = dp[i - 1] + nums[i];
    } else {
      dp[i] = nums[i];
    }
    if (result <= dp[i]) {
      result = dp[i];
    }
    System.out.println(" i = " + i + "  dp " + dp[i] + "    " + nums[i]);
  }
  return result;
}

一个for循序 ：

• 时间复杂度O(n)
• 空间复杂度O(1)