leetcode#53 最大子序和

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

审题

找到数组内连续的下标 相加最大值

第一次

暴力搜索，累加所有可能，计算最大值。

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = num[0];  // 必须初始化，防止负数
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            if (sum > max) {
                    max = sum;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum+=nums[j]
                max = sum > max ? sum : max;
            }
        }
      return max;
    }
}

第二次

最大子序和这道题重在思考，怎么才能一次遍历就出结果。从数字序列中观察可以发现，如果遇到正整数情况可以一直进行累加并比较最大值。

public class Solution {
    public int maxSubArray(int[] nums) {
          if (nums == null || nums.length == 0) return 0;
          // 注意不能初始化为 0 
          int max = nums[0];
          int sum = 0;
          for (int n : nums) {
                 // 无视 n == 0 情况
                 if (sum > 0) {
                      sum += n;
                 } else {
                      // 重置 sum，继续寻找下一个正整数
                      sum = n;
                 }
                 max = Math.max(sum, max);
          }
          return max;
    }
}