1、返回一个一维整数数组中最大子数组的和
要求： 输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)
思路：如果数组中的第二个数加上第一个数的和小于第二个数，那么舍弃第一个数
import java.util.Scanner; public class array { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); System.out.println("请输入数字的数量："); int n=scanner.nextInt(); int[] a=new int[n]; System.out.println("请输入数组的数值:"); for(int i=0;i<n;i++){ a[i]=scanner.nextInt(); } for(int i=1;i<n;i++){ if(a[i]+a[i-1]>a[i]) a[i]=a[i]+a[i-1]; } int ans=-1000; for(int i=0;i<n;i++) { if(a[i]>ans) ans=a[i];//找取最大值 } System.out.println(ans); } }
测试截图：
2、环状数组
要求：数组首尾相接，且数字不能重复使用
思路：在第一题的基础上，让a数组的每个数字开头组成n个新的b数组；
然后求出每个b数组的子数组的最大和，比较这n个数，最大的即为环状a数组的最大子数组和；
import java.util.Scanner; public class arrayCircle { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); System.out.println("请输入数字的数量："); int n=scanner.nextInt(); int[] a=new int[n]; System.out.println("请输入数组的数值:"); int m=-1000000; for(int i=0;i<n;i++) { a[i]=scanner.nextInt(); } for(int i=1;i<=n;i++) { int[] b=new int[n]; for(int j=0;j<n;j++) { b[j]=a[(i+j)%n];//让不同的数组开头，形成不同的数组 } m=max(arraymax(b,n),m);//调用函数，取出最大数值 } System.out.println("最大子数组的和为："+m); } //找出数组中和最大的 子数组 public static int arraymax(int[] a,int count) { for(int i=1;i<count;i++) { if(a[i]+a[i-1]>a[i]) a[i]=a[i]+a[i-1]; } int ans=-10000; for(int i=0;i<count;i++) { ans=max(ans,a[i]); } return ans; } public static int max(int ans,int i) { if(ans>i) return ans; else return i; } }
测试截图：
原文：https://www.cnblogs.com/xjmm/p/12374907.html