本文共 1561 字，大约阅读时间需要 5 分钟。

 分析:　可以在O(n)的时间复杂度之内解决问题，方式是在遍历的过程中记录乘积的最大值pos_value（大于等于０）和乘积最小值neg_value（小于等于０）。

初始时这些值设为0。

当遇到一个数a时:

若a为正数，pos_value为a（考虑pos_value为0的情况）与pos_value*a之中的较大的值。neg_value为neg_value与a的乘积(负数乘以一个正数会变得更小，若neg_value为0, 相乘之后仍然为0)

若a为负数,　pos_value为neg_value与a的乘积。neg_value为a(考虑pos_value为0的情况)与pos_value*a中的较小的值。

若a为0,则置pos_value与neg_value为0。

在以上过程中，所有pos_value中的最大的值即为答案。

代码如下：

int maxProduct(vector
   
    & nums) {    int size = nums.size();    if(size == 0)        return 0;    if(size == 1)        return nums[0];    int pos_value = 0, neg_value = 0;    int result = INT_MIN;    for(int i = 0; i < size; i++) {        if(nums[i] > 0) {            pos_value = max(nums[i], pos_value*nums[i]);  // pos可能为０            neg_value = neg_value*nums[i];        } else if(nums[i] < 0) {            int tmp = pos_value;            pos_value = neg_value*nums[i];            neg_value = min(nums[i],tmp*nums[i]); //pos可能为0        } else {            pos_value = 0;            neg_value = 0;        }        result = max(result, pos_value);    }    return result;}
   

分析: 需要注意到，这一题使用贪心算法无法找到最优解。比如说n=12时，贪心算法得到的值为12=9+1+1+1，结果为4,但实际上最优解为12=4+4+4,结果为3。

可以使用动态规划来解决问题：

dp[n] = min{dp[n-i*i]+1} 

其中dp[n]表示值为n时的最少个数。i为所有满足n-i*i>=0。当n-i*i=0时，表示n恰好可由i*i表示。另外,dp[0] = 0

代码如下：

int numSquares(int n) {    if(n == 0)        return 0;    vector
   
     dp(n+1, 0);    dp[1] = 1;    for(int i = 2; i <= n; i++) {        int min_value = INT_MAX;        for(int j = 1; j*j <= i; j++) {            min_value = min(dp[i-j*j]+1, min_value);        }        dp[i] = min_value;    }    return dp[n];}
   

转载地址：http://nwwob.baihongyu.com/