Given a matrix that contains doubles, find the submatrix with the largest product.

Return the product of the submatrix.

Assumptions

• The given double matrix is not null and has size of M * N, where M > = 1 and N > = 1

Examples

{ {1, -0.2, -1},

{1, -1.5, 1},

{0, 0, 1} }

the largest submatrix product is 1 * 1 = 1.

Solution: 类似largest submatrix sum。注意：double[] nums要对所有值设为1(默认为0); min, max, ans不能初始设为0或1，要设为nums[0]

  public double largest(double[][] matrix) {
    int m = matrix.length, n = matrix[0].length; 
    double result = matrix[0][0];
    for (int l = 0; l < m; l++) {
      double[] nums = new double[n];
      for (int k = 0; k < n; k++) {
          nums[k] = 1.0;
      }
      for (int j = l; j < m; j++) {
        for (int k = 0; k < n; k++) {
          nums[k] *= matrix[j][k];
        }
        //maximum subarray product
        double max = nums[0], min = nums[0], ans = nums[0];
        for(int i = 1; i < nums.length; i++){
          double temp = max;
          max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
          min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
          ans = Math.max(ans, max);
        }
        result = Math.max(result, ans);
      }
    }
    return result;
  }