本文共 1064 字，大约阅读时间需要 3 分钟。

题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路

两个map 

    m1储存A-B两端点值     m2存储A-max 从A出发最大连续数组和值     在两个for循环内部     一个count 用来记录连续的数组和值     一个max记录当期连续数组和值最大值

 

代码实现

public class demo{	public static void max(int[] xx) {				if(xx.length==0) {			System.out.println("数组为空");			return;		}				int max = 0;		int count = 0;				Map
   
     m1 = new HashMap<>();		Map
    
      m2 = new HashMap<>();		for(int i=0;i
     
      =max) {					max = count;					m1.put(i,j);					m2.put(i,count);				}			}			count = 0;		}		Set
      
       
        > s2 = m2.entrySet();				boolean flag = true;		int max2 = 0;		int index = 0;			for(Entry
        
          entry:s2) { if(flag==true) { max2 = entry.getValue(); flag = false; } if(max2<=entry.getValue()) { max2 = entry.getValue(); index = entry.getKey(); } } int index2 = m1.get(index); List
         
           list =new ArrayList<>(); for(int i=index;i<=index2;i++) { list.add(xx[i]); } System.out.println(list); } public static void main(String[] args) { int[] xx = {-2,1,-3,4,-1,2,1,-5,4}; max(xx); }}
         
        
       
      
     
    
   

 

转载地址：http://diazi.baihongyu.com/