题目:返回一个整数数组中最大子数组的和。
要求：
1.输入一个整形数组，数组里有正数也有负数。
2.数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
3.求所有子数组的和的最大值。要求时间复杂度为O(n)
设计思想：
1.首先输入数组数据；
2.将数组后一位与前一位相加，大于后一位，则后一位的加入有利，结果保留；小于后一位，则后一位的加入不利，结果不保留；
3.比较所有结果后，输出最大值。
代码实现：
#include <iostream>
using namespace std;
int main()
{
int a[100],i,n;
//1.首先输入数组数据
cout<<"输入数组所含数据个数：";
cin>>n;
cout<<"输入数据：";
for(i=1;i<=n;i++)
{
cin>>a[i];
}
//2.将数组后一位与前一位相加，大于后一位，则后一位的加入有利，结果保留；小于后一位，则后一位的加入不利，结果不保留
for(i=2;i<=n;i++)
{
if(a[i]+a[i-1]>a[i])
{
a[i]=a[i]+a[i-1];
}
}
//3.比较所有结果后，输出最大值
int ans=-100000;
for(i=1;i<=n;i++)
{
ans=max(ans,a[i]);
}
cout<<"子数组的和的最大值为：";
cout<<ans<<endl;
return 0;
}
运行截图：
一改：
数组为循环数组
思路：
1.遍历两遍；
2.增加子数组的数据个数，与总数据个数比较
代码实现：
#include <iostream>
using namespace std;
int main()
{
int a[100],i,n,b[2][200];
//1.首先输入数组数据
cout<<"输入数组所含数据个数：";
cin>>n;
cout<<"输入数据：";
for(i=1;i<=n;i++)
{
cin>>a[i];
}
int sign=1;//1.遍历两遍
b[0][1]=a[1];
b[1][1]=1;//2.增加子数组的数据个数，与总数据个数比较
//2.将数组后一位与前一位相加，大于后一位，则后一位的加入有利，结果保留；小于后一位，则后一位的加入不利，结果不保留
for(i=2;i<=n;i++)
{
if(sign==1)
{
if(a[i]+b[0][i-1]>a[i]&&b[1][i-1]<n)
{
b[0][i]=a[i]+b[0][i-1];
b[1][i]=b[1][i-1]+1;
}
else
{
b[0][i]=a[i];
b[1][i]=1;
}
if(i==n)//1.遍历两遍
{
i=0;
sign=0;
}
}
else
{
if(a[i]+b[0][i-1+n]>a[i]&&b[1][i-1+n]<n)
{
b[0][i+n]=a[i]+b[0][i-1+n];
b[1][i+n]=b[1][i-1+n]+1;
}
else
{
b[0][i+n]=a[i];
b[1][i+n]=1;
}
}
}
//3.比较所有结果后，输出最大值
int ans=-100000;
for(i=1;i<=2*n;i++)
{
ans=max(ans,b[0][i]);
}
cout<<"子数组的和的最大值为：";
cout<<ans<<endl;
return 0;
}
代码截图：
改二：
1.要求数组从文件读取。
2.如果输入的数组很大, 并且有很多大的数字, 就会产生比较大的结果 (考虑一下数的溢出), 请保证你的程序能正常输出。
3.另外, 如果输入文件的参数有错误, 这个程序应该能正常退出, 并显示相应的错误信息。 任何输入错误都不能导致你的程序崩溃。
代码实现：
package text;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
public class Third_text {
public static void main(String[] args) throws IOException {
double a[] = new double[50000000];
double b[] = new double[50000000]; // 用于储存子数组的最大值
/*文本数据写入*/
FileWriter fs = new FileWriter("D:\test.txt");
try {
Random random = new Random(System.currentTimeMillis());
for(int i=0;i<30000000;i++) {
int as = random.nextInt(1000)+1;
fs.write(as+" ");
}
}
catch (IOException e)
{
e.printStackTrace();
}
finally {
if(fs!=null)
fs.close();
}
/*文本数据导入*/
try (Scanner scanner = new Scanner(new BufferedReader(new FileReader(
"D:\test.txt")));) {
int n=0;
scanner.useDelimiter("[？|，|。|' ']");
while (scanner.hasNext()) {
double s = Double.parseDouble(scanner.next());
a[n]=s;
n++;
System.out.println(s);
if(n>=200000000) {
System.out.println("数据量过大！请重新设置一个小200000个的数组");
System.exit(0);
}
}
} catch (FileNotFoundException e) {
System.out.println("文件打开失败");
e.printStackTrace();
System.exit(0);
}
b[0] = a[0];
for (int i = 1; i < a.length; i++) {
b[i] = b[i - 1] + a[i];
}
double max = b[0];
int mas, mis;
mas = mis = 0;
double min = b[0];
/*比较这些子数组里的最大值和最小值*/
for (int i = 1; i < b.length; i++) {
if (max < b[i]) {
max = b[i];
mas = i;
}
if (min > b[i]) {
min = b[i];
mis = i;
}
}
/*判断最小子数组的成员个数是否大于最大子数组的成员个数*/
if (mis > mas) {
min = b[0];
mis=0;
for (int i = 0; i <= mas; i++) {
if (min > b[i]) {
min = b[i];
mis=i;
}
}
}
/*判断最小子数组的和值是否小于零*/
if(mis!=0)
{
if (min <= 0)
System.out.println("最大子数组的值为" + (max - min));
else
System.out.println("最大子数组的值为" + max);
}else
System.out.println("最大子数组的值为" + max);
}
}