|
输入一个整形数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)
|
上课思考了很久，这个问题看似简单，但是在电脑上实现就很难了，需要有一个很好的思维。
首先，数组得读取存写，读入之后进行求和计算并与原值比较，
开始的时候，因为题意的不明确（自己转的慢），首先确定几个关键词：连续子数组，和最大，时间复杂度。
这样，就可以下手了，将连续的数读入一个数组，从第一个数开始，与提前设定好的为零的tempsum相加，不影响，进行比较存储最大值，，进行for循环，直到最后一个数。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("输入数组个数：");
int n = sc.nextInt();
System.out.print("输入数组：");
int a[] = new int[n*2];
for(int i=0; i<n; i++)
{
a[i] = sc.nextInt();
}
for(int j=0;j<n-1;j++)
{
a[n+j]=a[j];
}
sc.close();
String intArrayString = Arrays.toString(a);
System.out.println(large(a,n));
}
private static int max(int a,int b) {
if(a>b) return a;
else return b;
}
private static int large(int a[],int n) {
int max=a[0];
int max2=0;
for (int i= 0; i<n*2; i++)
{
max2=max(max2+a[i],a[0]); //几个连续最大的值
max=max(max,max2);
}
return max;
}
代码就是这些代码，还有待改进，在思路上还要更清晰，这只是靠猜测，以及拼运气，没有绝对的信心。