Problem Description
Given a sequence a[1],a[2],a[3]……a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
DP问题。注意数组必须要开到100000以上才可以。
思路大体是开一个临时的子串并不断跟sum进行比较。复习一下动态规划再看。
代码:
#include#include #include #include #include #include using namespace std; int n, s, e; int a[100002]; int maxsub(int a[]) { s = e = 1; int sum, j, b, bs, be; sum = b = a[0]; for (j = 0; j = 0 && j != 0) { b = b + a[j]; be = j + 1; } else { b = a[j]; bs = j + 1; be = j + 1; } if (b>sum) { sum = b; s = bs; e = be; } } return sum; } int main() { int t, i, k = 1, sum; scanf(“%d”, &t); while (t–) { scanf(“%d”, &n); for (i = 0; i 另一版本
#includeusing namespace std; int *arr, first, last, sum; void MaxSub(int *arr, int count, int &first, int &last, int ∑) { //tFirst,tSum为临时的最大子序列的第一个元素与和 int tFirst, tSum, i; //初始化 first = tFirst = last = 0; sum = tSum = arr[0]; //遍历该数组 for (i = 1; i = 0) tSum += arr[i]; else { tSum = arr[i]; tFirst = i; } //如果临时的最大值大于实际的最大值,则更新子序列的first, last, sum if (sum < tSum) { sum = tSum; first = tFirst; last = i; } } } int main() { int num, n, i, j; bool top = true; cin >> num; for (j = 0; j > n; arr = new int[n]; for (i = 0; i > arr[i]; MaxSub(arr, n, first, last, sum); if (top) top = false; else cout << endl; cout << "Case " << j + 1 << ":" << endl << sum << " " << first + 1 << " " << last + 1 << endl; delete[] arr; } return 0; } //求最大子序列之和,arr是原来的数组,count是数组的元素个数, //first,last是所求子序列的第一个元素,最后一个元素的下标,sum是所求子序列的元素之和 部分参考自网络。
发表回复