2014-05-10 20:31

題目鏈接

原題：

Given an array of integers and a length L, find a sub-array of length L such that the products of all integers are the biggest. Example: Input: {4, 1, -7, -8, 9}, 3 Output: {-7,-8,9}

題目：給定一個整數數組，其中包含正數、負數或者0。請找出乘積最大的子數組(子數組是連續的，子序列可以不連續)。不過，此處限制子數組的長度為L。

解法：因為限制了子數組的長度為L，問題解法瞬間就變了。如果沒有長度限制，這應該是個比“最大子數組和”更難的動態規劃。限制了長度為L以后，我們可以直接順序計算每個長度為L的子數組的乘積。這種算法可以在線性時間內完成。不過缺點也是顯而易見的：連乘一堆整數，很容易就溢出了。暫時還沒想出能夠不計算乘積就得出結果的辦法，等我想到了再來更新這篇解題報告吧。

代碼：

1 // http://www.careercup.com/question?id=5752271719628800 2 #include <climits> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 7 int maxSubarrayProduct(vector<int> &v, int k) 8 { 9 int n = (int)v.size(); 10 11 if (n == 0) { 12 return -1; 13 } 14 if (k >= n) { 15 return 0; 16 } 17 18 int i, ll; 19 long long int product; 20 long long int max_product = INT_MIN; 21 22 int j; 23 i = 0; 24 while (i + k <= n) { 25 product = 1; 26 for (j = i; j < i + k; ++j) { 27 if (v[j] == 0) { 28 product = 0; 29 break; 30 } else { 31 product *= v[j]; 32 } 33 } 34 if (product > max_product) { 35 max_product = product; 36 ll = i; 37 } 38 if (j < i + k) { 39 i = j + 1; 40 } else { 41 ++i; 42 while (i + k <= n && v[i + k - 1] != 0) { 43 product = product / v[i - 1] * v[i + k - 1]; 44 if (product > max_product) { 45 max_product = product; 46 ll = i; 47 } 48 ++i; 49 } 50 if (i + k <= n) { 51 if (max_product < 0) { 52 max_product = 0; 53 ll = i; 54 } 55 i = i + k; 56 } 57 } 58 } 59 60 return ll; 61 } 62 63 int main() 64 { 65 int i; 66 int n; 67 int k; 68 int ll; 69 vector<int> v; 70 71 while (cin >> n && n > 0) { 72 v.resize(n); 73 for (i = 0; i < n; ++i) { 74 cin >> v[i]; 75 } 76 cin >> k; 77 k = k < n ? k : n; 78 ll = maxSubarrayProduct(v, k); 79 cout << '{'; 80 for (i = 0; i < k; ++i) { 81 i ? (cout << ' '), 1 : 1; 82 cout << v[i + ll]; 83 } 84 cout << '}' << endl; 85 v.clear(); 86 } 87 88 return 0; 89 }

?

轉載于:https://www.cnblogs.com/zhuli19901106/p/3720992.html

總結

以上是生活随笔為你收集整理的Careercup - Microsoft面试题 - 5752271719628800的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。