sum 遍历 int img imp ext clas 数组
题目要求:
1、输入一个一维整形数组,数组里有正数也有负数。
2、一维数组首尾相接,象个一条首尾相接带子一样。
3、数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。
设计思想:
遍历数组里面的每一个数将第一个数变为最后一个数,具体算法 a[i-1]=a[i], 这样又变成了一个新的一维数组,输出每个数组的最大子数组和,然后比较每个输出的和,找出最大的数
代码:
- import java.util.Scanner;
- public class shuzu {
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Scanner scan=new Scanner(System.in);
- System.out.print("请输入数组中数字的个数:");
- int n=scan.nextInt();
- int[] a=new int [n];
- System.out.print("请输入数组:");
- for(int i=0;i<n;i++)
- {
- a[i]=scan.nextInt();
- }
- int a1=findMaxSum(a,n);
- int b,temp,i,sum=0;
- for(b=1;b<n;b++)
- {
- temp=a[0];
- for(i=1;i<=n-1;i++)
- {
- a[i-1]=a[i];
- }
- a[n-1]=temp;
- if(findMaxSum(a,n)>=sum)
- {
- sum=findMaxSum(a,n);
- }
- }
- int a2=sum;
- if(a1>=a2)
- {
- System.out.println("最大子数组和:" + a1);
- }
- else
- {
- System.out.println("最大子数组和:" + a2);
- }
- }
- public static int findMaxSum(int a[],int n)
- {
- int sum=0;
- int b=0;
- for(int i=0; i<n; i++)
- {
- if(b<0)
- b=a[i];
- else
- b+=a[i];
- if(sum<b)
- sum=b;
- }
- return sum;
- }
- }
运行结果截图:
首尾相连求最大子数组和
来源: http://www.bubuko.com/infodetail-2002370.html