题目:

  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.

题意:

  题目中给出一个(至少包含一个元素)整形数组,求一个子数组(元素连续),使得其元素之积最大。

  最直接了当的方法,当然是暴力穷举,但是其O(n^2)是无法通过LeetCode的OJ的。

  以下给出了本题的解决方法,O(n)时间复杂度,C++实现。

 class Solution {
public:
int maxProduct(int A[], int n) {
int nMaxPro = A[];
int max_tmp = A[];
int min_tmp = A[]; for(int i = ; i< n; ++i){
int a = A[i] * max_tmp;
int b = A[i] * min_tmp; max_tmp = (( a > b ? a : b ) > A[i]) ? ( a > b ? a : b ) : A[i];
min_tmp = (( a < b ? a : b ) < A[i]) ? ( a < b ? a : b ) : A[i]; nMaxPro = (nMaxPro > max_tmp) ? nMaxPro : max_tmp;
} return nMaxPro;
}
};

运行结果:

希望各位看官不吝赐教,小弟感谢~!

最新文章

  1. SQL SERVER 通用分页存储过程,两种用法任你选
  2. EEG preprocess - re-reference EEG预处理 - 重参考
  3. TypedReference
  4. jQuery语法
  5. 触发隐藏链接进行文件下载,click无响应
  6. 1069: [SCOI2007]最大土地面积 - BZOJ
  7. linux-阿里云ECS部署PPTP(centos)
  8. asp.net项目中通过Web.config配置文件及文件夹的访问权限---forms
  9. python 学习笔记整理
  10. TSQL编程
  11. Even Parity uva11464 模拟
  12. linux 安装icu库
  13. defaultdict的威力
  14. Linux SVN安装
  15. .Net Core 读取配置文件 appsettings.json
  16. Flask 构建微电影视频网站(三)
  17. vmware + centos 7安装vmtools时提示The path "" is not a valid path to the xxx kernel header
  18. 学习 MeteoInfo二次开发教程(四)
  19. windows nodejs yarn 与hadoop yarn命令冲突
  20. JDK源码分析(4)HashSet

热门文章

  1. [官方教程] [ES4封装教程]1.使用 VMware Player 创建适合封装的虚拟机
  2. Linux 面试题总结
  3. Android自动登录与记住密码
  4. Tornaod框架
  5. Lucas的数论(math)
  6. JSON: property &quot;xxx&quot; has no getter method in class &quot;...&quot;
  7. Android app主线程UI更新间歇性崩溃的问题
  8. Sybase IQ如何将大文件数据迅速加载到数据库
  9. 用php实现遍历目录
  10. Java for LeetCode 052 N-Queens II