给定由 n 个整数组成的序列(a1, a2, …, an),求该序列形如
的子段和的最
大值,当所有整数均为负整数时,其最大子段和为 0。扩展要求:找出最大字段和的下标
范围。
程序:
package ch5;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class MaxSum {
public static int left;
public static int right;
public static int maxsum(ArrayList<Integer>
a,ArrayList<Integer> b) {
for(int i=1; i<a.size(); i++)
{
if(b.get(i-1)<=0)
{b.set(i, a.get(i));//将 list b 的第 i 个位置赋
值,值为 list a 的第 i 个位置的数字
left=i+1;
}
else
{ b.set(i, b.get(i-1)+a.get(i));//将 list b 的
第 i 个位置赋值,值为 list b 的第 i-1 个位置数字+list a 的第 i 个位置
的数字
right=i+1;
}
}
return Collections.max(b); //Collections 类的
max() 方法可以获取 List 中的最大最小值
}
public static void main(String []args) {
System.out.println("请输入一串测试数字:");
Scanner scan=new Scanner(System.in);
评论10