Careercup

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 }