首页 > 其他 > 详细

Leetcode: maximum product subarray

时间:2015-08-11 09:41:59      阅读:216      评论:0      收藏:0      [点我收藏+]

August 10, 2015

有二种解法, Greedy算法, 和DP算法. 二种算法都通过leetcode online judge. 贪婪算法, 花了一个小时理解代码, 修改后很好理解. 

Problem statement:

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.

Two approaches, one is dynamic programming DP implementation, another is the greedy method.

DP solution:

https://github.com/jianminchen/MaximumProductSubarray/blob/master/MaximumProductSubarray1.cs

Greedy algorithm:

https://github.com/jianminchen/MaximumProductSubarray/blob/master/MaximumProductSubarray2.cs

Leetcode: maximum product subarray

原文:http://www.cnblogs.com/juliachenOnSoftware/p/4719930.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!