snapchat跪经

请问楼主第一题数字中间可以不加任何符号嘛？

小A要当码农 发表于 2016-9-20 03:59
请问楼主第一题数字中间可以不加任何符号嘛？

不可以
字数字数字数

zzgzzm 发表于 2016-9-18 10:53
第一题：确认一下，给定的数组vector arr顺序是不能改变的吧。let dp(i, k) be the max value calculated f ...

这个貌似是正确的，但是复杂度好像比较高，O(n3)？

我想的办法是dp(i)表示到第i个数的值，dp(i) = max(dp(j) + a[j+1]*a[j+2]*...*a[i])，也就是计算dp(i)时，枚举上一个加号的位置（从后往前数）。这个是O(n2)的。

qesss 发表于 2016-9-27 00:50
这个貌似是正确的，但是复杂度好像比较高，O(n3)？

我想的办法是dp(i)表示到第i个数的值，dp(i) = max ...

Yes, you are right! Using 1D dp is enough (which yields O(n^2) time complexity only) by looking for the LAST plus sign (instead of any plus sign). Looking for the last plus signs requires only to calculate result from first a[0] to some a[i] with fix starting point.

第一题能加括号么

zzgzzm 发表于 2016-9-28 13:33
Yes, you are right! Using 1D dp is enough (which yields O(n^2) time complexity only) by looking fo ...

这一题能不能LC282的解法呀，backtracking，把最后一个加上的数字传下去。。

请问楼主第二题啥思路呀。。。给的链接好像不对啊。。。

小A要当码农 发表于 2016-10-9 12:06
这一题能不能LC282的解法呀，backtracking，把最后一个加上的数字传下去。。

The idea is similar to LC282. However, this problem has no target value. Let dp[i] note the max value we could get from partial array of first several consecutive entries. Then the key is to check where should we insert the last "+" or not to use "+" at all (i.e., insert "*" for all positions).

1. int getPlusMultiplyMax(vector<int>& a) {
   
2.   int n = a.size();
   
3.   if (n == 0) return INT_MIN; // default answer for empty array
   
4. 
   
5.   // dp[i]: max value generated from a[0],...,a[i]  
   
6.   vector<int> dp(n); dp[0] = a[0];
   
7.   for (int i = 1; i < n; ++i) dp[i] = a[i]*dp[i-1];
   
8.   for (int i = 1; i < n; ++i) {
   
9.     int lastProduct = 1;
   
10.     for (int j = i-1; j >= 0; j--) {
    
11.       lastProduct *= a[j+1];
    
12.       dp[i] = max(dp[j], dp[j] + lastProduct);
    
13.     }
    
14.   }
    
15.   return dp[n-1];
    
16. }

复制代码

补充内容 (2016-10-10 07:29):
Actually, I think this problem is easier than LC282 since we don't need to worry about matching target value or special treatment for "*" which is precedent to "+" operator in calculation.