数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法律学使用 O(n^2) 时间（朴素方法）查找最大子数组和的 C++ 程序
我们将开发一个 C++ 程序来查找最大子数组和 O(n^2) 时间（朴素方法）。
算法
Begin Take the array elements as input. Make a loop for the length of the sub-array from 1 to n, within this loop, Make another loop nested with the previous one, calculate the sum of first sub-array of that length. For remaining sub-array sum, add the next element to the sum and subtract the first element of that sub-array. Compare it with the global max and update if found out to be more. Print the max sub-array and their sum as a result. End.
示例代码
#include<iostream>
using namespace std;
int main() {
int n, i, j, m=-1, s, ini_m, fi_m;
cout<<"\nEnter the number of data element in the array: ";
cin>>n;
int a[n];
for(i = 0; i < n; i++) {
cout<<"Enter element "<<i+1<<": ";
cin>>a[i];
}
for(i = 1; i < n+1; i++) {
s = 0;
for(j = 0; j < n; j++) {
if(j < i)
s += a[j];
else
s = s+a[j]-a[j-i];
if(m< s) {
ini_m = j-i+1;
fi_m = j;
m = s;
}
}
}
cout<<"\nThe maximum sub array is: ";
for(i = ini_m; i <= fi_m; i++)
cout<<a[i]<<" ";
cout<<"\nThe maximum sub-array sum is: "<<m;
}输出
Enter the number of data element in the array: 10 Enter element 1: 1 Enter element 2: -2 Enter element 3: 3 Enter element 4: -4 Enter element 5: 5 Enter element 6: -6 Enter element 7: 7 Enter element 8: 8 Enter element 9: -9 Enter element 10: 10 The maximum sub array is: 7 8 -9 10 The maximum sub-array sum is: 16
更新时间：2019-07-30
270 浏览
广告