要求:
输入一个整形数组,数组里面有正数也有负数。
数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
求虽有子数组的和的最大值。要求时间复杂度为O(n)。
设计思想:
开辟一个数组空间,然后存入指定数量的数组
在数组中先选取一个点,然后在这个点之后再选取第二个点,
用用循环将两个点之间的数相加求和,并和之前的数相比较得出最大的子数组的和。
编写过程中通过查询网上的资料 学习了额如何手动输入定义数组的长度。(int *array = new int[100];//-----开辟空间)
代码:
#include<iostream> #include<cmath> using namespace std; int main() { int i,j,k,n,he;//---he(子数组的和) k = 0; cout << "请输入数组的个数:"; cin >> n; int *array = new int[100];//-----开辟空间 cout << "请输入一个数组:" << endl; for (i = 0; i < n; i++) { cin >> array[i]; } int max = array[0];//---初始化最大值 for (i = 0; i < n; i++)//-------第一个点.a0.a1.a2.a3.a4 { for (j = i+1; j < n+1; j++)//--------第二个点a0.a1.a2.a3.a4. { int k = {}; for (int l = i; l < j; l++)//------子数组求和 { k = k+array[l]; } if (max < k) { max = k; } } } cout << max; return 0; }
结果截图:
总结:基础还是太差 编程经验太少,需要大量的基础知识。还是要多看书啊。。。。
原文:http://www.cnblogs.com/3712k/p/5302917.html