首页 / 操作系统 / Linux / 编程算法 - 连续和最大的子数组 代码（C）

连续和最大的子数组 代码（C） 

题目: 在一个数组中, 找出连续和最大的子序列.使用两个变量, 一个变量存储当前值, 一个变量存储最大值, 并设一个临时数组, 用于更新最大和数组.时间复杂度O（n）.代码:/*
 * main.cpp
 *
 *  Created on: 2014.9.19
 *      Author: spike
 */#include <iostream>
#include <vector>
#include <climits>using namespace std;int FindSequence （int data[], int length, vector<int>& vi）{
 if （data == NULL || length <= 0）
  return INT_MIN;
 int greatest = INT_MIN;
 int cur = 0;
 vector<int> tmp; for （int i=0; i<length; ++i） {
  if （cur <= 0） {
   cur = data[i];
   tmp.clear（）;
   tmp.push_back（data[i]）;
  } else {
   cur += data[i];
   tmp.push_back（data[i]）;
  }  if （cur > greatest） {
   vi = tmp;
   greatest = cur;
  }
 }
 return greatest;
}int main（void）
{
 int data[] = {1, -2, 3, 10, -4, 7, 2, -5};
 int length = sizeof（data）/sizeof（data[0]）;
 vector<int> vi;
 int g = FindSequence（data, length, vi）;
 cout << g << ": ";
 for （size_t i=0; i<vi.size（）; ++i） {
  cout << vi[i] << " ";
 }
 cout << endl;    return 0;
}输出:18: 3 10 -4 7 2本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-10/107628.htm