首页 > 其他 > 详细

LeetCode 343

时间:2016-05-10 20:38:32      阅读:150      评论:0      收藏:0      [点我收藏+]

Integer Break

Given a positive integer n, break it into the sum of at least two positive integers
and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: you may assume that n is not less than 2.

Hint:

There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.

 

 1 /*************************************************************************
 2     > File Name: LeetCode343.c
 3     > Author: Juntaran
 4     > Mail: Jacinthmail@gmail.com
 5     > Created Time: Tue 10 May 2016 04:17:35 PM CST
 6  ************************************************************************/
 7  
 8 /*************************************************************************
 9     
10     Integer Break
11     
12     Given a positive integer n, break it into the sum of at least two positive integers 
13     and maximize the product of those integers. Return the maximum product you can get.
14 
15     For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).
16 
17     Note: you may assume that n is not less than 2.
18 
19     Hint:
20 
21     There is a simple O(n) solution to this problem.
22     You may check the breaking results of n ranging from 7 to 10 to discover the regularities.
23 
24  ************************************************************************/
25 
26 #include<stdio.h>
27 
28 int integerBreak( int n )
29 {
30     if( n <= 2 )
31     {
32         return 1;
33     }
34     if( n == 3 )
35     {
36         return 2;
37     }
38     int ret = 1;
39     while( n > 4 )
40     {
41         ret *= 3;
42         n -= 3;
43     }
44     return ret*n;
45 }
46 
47 int main()
48 {
49     int n = 7;
50     int ret = integerBreak(n);
51     printf("%d\n",ret);
52 
53     return 0;
54 }

 

LeetCode 343

原文:http://www.cnblogs.com/Juntaran/p/5479118.html

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