Chinaunix首页 | 论坛 | 博客
  • 博客访问: 104733
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: Java

2014-12-29 15:59:57

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

******************************************************************

分析:

    1、特殊情况0,因为0 的相乘特性会使所有的数都变为0,所以在这个题目中会起到隔断作用。可以用一个值来存储历史最大值实时更新
    2、排除了0以后,连续的正数相乘得到的是最大数,如果有负数就可能直接变为最小数,那么也就是说最小数可以变为最大数,最大数也可能变为最小数。
    3、对于局部的最大值,可以从正数开始乘,如果足够大就保存到全局的最大值中。
******************************************************************
代码:

点击(此处)折叠或打开

  1. public static int maxProduct(int[] A) {
  2.         if (A == null || A.length == 0)
  3.             return 0;
  4.         if (A.length == 1)
  5.             return A[0];
  6.         int max_local = A[0];
  7.         int min_local = A[0];
  8.         int global = A[0];
  9.         for (int i = 1; i < A.length; i++) {
  10.             int max_copy = max_local;
  11.             // 计算非0段的最大乘积(全是正数,或者 包含偶数个负数)
  12.             max_local = Math.max(Math.max(A[i] * max_local, A[i]), A[i]
  13.                     * min_local);
  14.             // 计算非0段的最小乘积(奇数个负数以及若干个正数)
  15.             min_local = Math.min(Math.min(A[i] * max_copy, A[i]), A[i]
  16.                     * min_local);
  17.             // 保存历史最大乘积值
  18.             global = Math.max(global, max_local);
  19.         }
  20.         return global;
  21.     }


阅读(414) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册