1、贪心算法

  1. /**
  2.    * https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
  3.    * @param nums
  4.    * @return
  5.    */
  6.   public static  int maxSubArray(int[] nums) {
  7.     /*
  8.     思路：
  9.      动态规划，遍历数组，当前最大子序和为sum，结果为res
  10.      当sum>0 说明对结果有增益作用，则sum保留，并且sum+=nums[i]
  11.      当sum<=0 说明对结果没有增益作用，则舍弃，同时sum=num[i]
  12.      每次遍历比较sum、res，取最大值返回
  13.      */
  14.     int sum=0;
  15.     int res=nums[0];
  16.     for (int i = 0; i < nums.length; i++) {
  17.       if(sum>0){
  18.         sum+=nums[i];
  19.       }else{
  20.         sum = nums[i];
  21.       }
  22.       res = Math.max(sum,res);
  24.     }
  25.     return res;
  26.   }
  28.   public static void main(String[] args) {
  29.    int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
  30.     System.out.println(_动态规划.maxSubArray(nums));
  31.   }

2、动态规划

  1. /**
  2.    * 采用动态规划
  3.    * 思路：
  4.    * 定义一个数组int[] dp, dp[i] 表示i位置的最大子序列和
  5.    * dp[i] = max(num[i], dp[i-1]+num[i])
  6.    * 最后返回dp中的最大值
  7.    * @param nums
  8.    * @return
  9.    */
  10.   public static  int maxSubArrayDP(int[] nums) {
  11.     int[] dp = new int[nums.length];
  12.     dp[0] = nums[0];
  13.     int max = 0;
  14.     for (int i = 1; i < nums.length; i++) {
  15.       dp[i] = Math.max(nums[i], nums[i]+dp[i-1]);
  16.       max = Math.max(max,dp[i]);
  17.     }
  18.     return max;
  19.   }