152. 乘积最大子序列

递归解法 不过超时了 改为动态规划

class Solution {
  //递归
  public int maxProduct(int[] nums) {
      return selectMax(1,nums,nums[0]);
  }
  public int selectMax(int x ,int nums[],int flag) {
      if(x==nums.length) {
          return flag ;
      }
      else {
          return Math.max(
              Math.max(selectMax(x+1,nums,flag*nums[x]),selectMax(x+1,nums,nums[x]))
              ,flag);
      }
  }
}

动态规划

class Solution {
  //动态规划
  public int maxProduct(int[] nums) {
      int n = nums.length;
      if (n == 0) {
          return 0;
      }
      // 因为两种状态 所以需要同时记录最大值和最小值
      int max = nums[0];
      int f1[] = new int[n]; //max
      f1[0] = nums[0];
      int f2[] = new int[n]; //min 
      f2[0] = nums[0];

      for(int i = 1 ; i < n ; i++) {
          f1[i] = Math.max(nums[i], Math.max(f1[i-1]*nums[i], f2[i-1]*nums[i]));
          f2[i] = Math.min(nums[i], Math.min(f1[i-1]*nums[i], f2[i-1]*nums[i]));
          max = Math.max(max, f1[i]);
      }
      return max;
  }
}

动态规划

class Solution {
  //动态规划
  public int maxProduct(int[] nums) {
      int n = nums.length;
      int max  = Integer.MIN_VALUE;
      int imax = 1 ;
      int imin = 1;
      for(int i = 0 ; i < n ;i++) {
          if(nums[i]<0) {
              int temp = imax;
              imax = imin;
              imin = temp;
          }
          imax = Math.max(nums[i], imax*nums[i]);
          imin = Math.min(nums[i], imin*nums[i]);
          max = Math.max(imax, max);
      }
      return max;
  }
}