黑马程序员技术交流社区

标题: 程序员面试100题之九：求子数组的最大和 [打印本页]

---

作者: 奋斗_168    时间: 2015-4-9 17:27
标题: 程序员面试100题之九：求子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
       例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

---

作者: kapp_tolo    时间: 2015-4-9 18:00
不知道呀，很多看不懂呀，你是什么基础呀。

---

作者: 剑雨飘扬    时间: 2015-4-9 18:38
对数组从左到右相加求和，当和的最小值在最大值左边时，和的最小值到最大值之间的子串即为最大子串；
当和的最小值在最大值的右边时，把数组分成三段：
0~最大值坐标，最大值坐标~最小值坐标，最小值坐标~array.length
这三段中的最大子串就是整个数组的最大子串 。
优点：当数组和的最小值在最大值左边时，计算量比较少(只是求一遍和)，速度快。

这是我的想法，不知道有没有更好的算法。

---

作者: 只吃饭不洗碗    时间: 2015-4-9 21:29
   //由于求和要对该数组的所有子集都操作一遍，考虑将子集放入到集合里。
import java.util.*;

           class Test
           {
                   public static void main(String[] args)
                   {
                           //定义一个装整型数组的ArrayList集合，放入数组的所有子集
                           // ArrayList<int[]> al = new ArrayList<int[]>();

                                int[] arr = {1,-2,3,10,-4,7,2,-5};

                                //al = getSubArrays(arr);

                                int maxSum = getMaxSumArray(arr);
                                System.out.println("maxSum = "+maxSum);
                               
                               
                   }

                   /*
                        定义一个功能，找出子数组和的最大值
                   */
                   public static int getMaxSumArray(int[] arr)
                   {
                                //定义一个装整型数组的ArrayList集合，放入数组的所有子集
                            ArrayList<int[]> al = new ArrayList<int[]>();
                                al = getSubArrays(arr);
                                int maxSum = arraySum(al.get(0));
                                for (Iterator<int[]> it = al.iterator();it.hasNext() ; )
                                {
                                        int[] temp = it.next();
                                        if (arraySum(temp)>maxSum)
                                        {
                                                maxSum = arraySum(temp);
                                        }
       
                                }return maxSum;
                   }


                   /*
                        定义一个给数组求和的功能
                   */
                   public static int arraySum(int[] arr)
                   {
                                int sum = 0;
                                for (int x=0;x<arr.length ;x++ )
                                {
                                        sum = sum+arr[x];
                                }return sum;
                   }
                       
                        /*
                         定义一个获取数组所有子集的功能
                        */
                   public static ArrayList<int[]> getSubArrays(int[] arr)
                   {
                           ArrayList<int[]> al = new ArrayList<int[]>();
                          
                                for (int x=0;x<arr.length ;x++ )
                                {
                                        for (int y=0,z=arr.length-x;z!=arr.length+1 ;y++,z++ )
                                        {
                                                int[] temp = Arrays.copyOfRange(arr,y,z);
                                                al.add(temp);

                                        }
                                }return al;
                   }
                  
           }

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2