广州多益网络2013校园招聘上机笔试题目3

#include <iostream> using namespace std; //寻找整型数组的最大连续子数组，并输出起止位 //由于加上一个数使子数组变大，减去一个数使子数组变小 //遍历过程中，中间变量tmp为负时，丢弃已经遍历的和 int MaxSubArray(int data[], int size, size_t &beg, size_t &end) { int tmp = 0; int maxvalue = 0; size_t tmp_beg = 0; for (size_t i = 0; i < size; i++) { tmp += data[i]; if (tmp < 0) { tmp = 0; tmp_beg = i + 1; } if (tmp > maxvalue) { maxvalue = tmp; end = i; if (tmp_beg <= end) { beg = tmp_beg; } } } //全负数的情况 if (maxvalue == 0) { maxvalue = data[0]; for (size_t j = 0; j < size; j++) { if (data[j] > maxvalue) { maxvalue = data[j]; beg = end = i; } } } return maxvalue; } int main() { int data[] = {-1, 98, 8, 76, -23, -988, 22, 12, 32, 48, 23, 23 ,23, -8 -987}; size_t beg = 0; size_t end = 0; cout << MaxSubArray(data, sizeof(data)/sizeof(data[0]), beg, end) << endl; if (beg == end) { cout << beg << endl; } else { cout << beg << " " << end << endl; } return 0; }