14 - I（343） 剪绳子
给你一根长度为 $n$ 的绳子，请把绳子剪成整数长度的 $m$ 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 $k[0],k[1]...k[m-1]$ 。请问 $k[0]*k[1]*...*k[m-1]$ 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示：
- $2 <= n <= 58$
题解
/*dp343*/
/*
dp五部曲:
1.状态定义:dp[i]为长度为i的绳子剪成m段最大乘积为dp[i]
2.状态转移:dp[i]有两种途径可以转移得到
2.1 由前一个dp[j]*(i-j)得到,即前面剪了>=2段,后面再剪一段,此时的乘积个数>=3个
2.2 前面单独成一段,后面剩下的单独成一段,乘积为j*(i-j),乘积个数为2
两种情况中取大的值作为dp[i]的值,同时应该遍历所有j,j∈[1,i-1],取最大值
3.初始化:初始化dp[1]=1即可
4.遍历顺序:显然为正序遍历
5.返回坐标:返回dp[n]
*/
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[1]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=i-1;j++)
{
int tmp = max(dp[j]*(i-j),j*(i-j));
dp[i] = max(tmp, dp[i]);
}
}
return dp[n];
}
};14 - II（343） 剪绳子 II
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36提示：
2 <= n <= 1000
题解
class Solution {
public int cuttingRope(int n) {
if(n <= 3)
return n - 1;
int b = n % 3, p = 1000000007;
long ret = 1;
int lineNums=n/3; //线段被我们分成以3为大小的小线段个数
for(int i=1;i<lineNums;i++) //从第一段线段开始验算，3的ret次方是否越界。注意是验算lineNums-1次。
ret = 3*ret % p;
if(b == 0)
return (int)(ret * 3 % p); //刚好被3整数的，要算上前一段
if(b == 1)
return (int)(ret * 4 % p); //被3整数余1的，要算上前一段
return (int)(ret * 6 % p); //被3整数余2的，要算上前一段
}
}
63（121） 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。限制：
0 <= 数组长度 <= 10^5题解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int cost = __INT_MAX__, profit=0;
for(int price: prices)
{
cost = min(cost, price);
profit = max(profit,price - cost);
}
return profit;
}
};
