首页 > 代码库 > leetcode-Maximum Product Subarray zz
leetcode-Maximum Product Subarray zz
LinkedIn 高频题 – Maximum Sum/Product Subarray
Maximum Sum Subarray是leetcode原题,跟Gas Station的想法几乎一模一样。解答中用到的结论需要用数学简单地证明一下。
1 2 3 4 5 6 7 8 9 10 11 12 | public int maxSubArray( int [] A) { int sum = 0 ; int max = Integer.MIN_VALUE; for ( int i = 0 ; i < A.length; i++) { sum += A[i]; if (sum > max) max = sum; if (sum < 0 ) sum = 0 ; } return max; } |
Maximum Product Subarray其实只需要不断地记录两个值,max和min。max是到当前为止最大的正product,min是到当前为止最小的负product,或者1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public int maxProduct( int [] A) { int x = 1 ; int max = 1 ; int min = 1 ; for ( int i = 0 ; i < A.length; i++) { if (A[i] == 0 ) { max = 1 ; min = 1 ; } else if (A[i] > 0 ) { max = max * A[i]; min = Math.min(min * A[i], 1 ); } else { int temp = max; max = Math.max(min * A[i], 1 ); min = temp * A[i]; } if (max > x) x = max; } return x; } |
http://shepherdyuan.wordpress.com/2014/07/23/linkedin-maximum-sumproduct-subarray/
leetcode-Maximum Product Subarray zz
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。