java求最大数组和

不念不忘少年蓝@ 2021-11-09 04:48 329阅读 0赞

**1. 项目要求**

*  最大子数组和问题的源程序代码；
 *  运行界面截图；
 *  算法设计结果，自行选择相应的工具进行表达；
 *  单元测试的构建，在集成开发工具中完成，至少达到分支覆盖标准；
 *  对程序进行效能分析，生成分析报告。

**2. 算法设计**

方法一：可以[从头到尾][Link 1]遍历，遍历过程中，对以每个元素开头的子数组求连续最大和，最后从各个最大[和中][Link 2]找出最大的。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70][]

方法二：使用动态规划的方法，先以第一个数为局部最大和整体最大值，之后遍历数组，累加到局部最大值上，若新加上的数比局部最大值还要大，则把这个新数作为局部最大值，直到遍历结束；遍历过程中，若局部最大值大于整体最大值，则赋值给整体最大值。

举例：

*  6，-3，-2，7，-15，1，2，2（max局部最大=res全局最大=6）
 *  max=6+(-3)>(-3)=3 ; res=6
 *  max=3+(-2)>(-2)=1 ; res=6
 *  max=1+7>7=8 ; res=8
 *  ......

特别地：

*  1，-2，3，10，-4，7，2，-5（max=res=1）
 *  max=1+(-2)>(-2)=-1 ; res=1
 *  max=(-1)+3<3=3 ; res=3
 *  ......

**3. 源代码**

package pigeon;
    /**
     * @param array 输入数组
     * @return 连续子数组的最大和
     * @author pigeon
     */
    public class FindGreatestSumOfSubArray {   //从头至尾遍历
    	public int FindGreatestSumOfSubArray1(int[] array){
    		int max = -99999;
    		for(int i=0; i<array.length; i++){
    			int temp1 = 0;
    			for(int j=i; j<array.length; j++){
    				temp1 += array[j]; 
    				if(temp1 > max){
    					max = temp1;
    				}
    			}			
    		}
    		return max;
    	}
    	public int FindGreatestSumOfSubArray2(int[] array){  //动态遍历
    		int max = array[0];
    		int res = array[0];
    		for(int i=1; i<array.length; i++){
    			max = (max+array[i]) > array[i] ? max+array[i] : array[i];
    			res = max>res ? max : res;
    		}
    		return res;
    	}	
    	public static void main(String[] args) {
    		int[] array = {1,-2,3,10,-4,7,2,-5};
                    FindGreatestSumOfSubArray test = new FindGreatestSumOfSubArray();
    		System.out.println(test.FindGreatestSumOfSubArray1(array));
    	        System.out.println(test.FindGreatestSumOfSubArray2(array));	
            }
    }

**4. 运行结果**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 1][]

**5. 测试代码**

package Find;
    import static org.junit.jupiter.api.Assertions.*;
    import org.junit.jupiter.api.Test;
    import pigeon.FindGreatestSumOfSubArray;
    
    class FindGreatestSumOfSubArrayTest {
    	@Test
    	void testFindGreatestSumOfSubArray1() {
                FindGreatestSumOfSubArray test = new FindGreatestSumOfSubArray();	        
                int arr1[]= {0,0,0,0,0,0};
    	    assertTrue(test.FindGreatestSumOfSubArray1(arr1)==0);
    	}
    	@Test
    	void testFindGreatestSumOfSubArray2() {
                FindGreatestSumOfSubArray test = new FindGreatestSumOfSubArray();	
    	    int arr2[]= {-1,-2,3,8,-4,6,-9};
                assertTrue(test.FindGreatestSumOfSubArray2(arr2)==13);
    	}
    }

**6. 测试结果**

**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 2][]**![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 4][]

[Link 1]: https://www.baidu.com/s?wd=%E4%BB%8E%E5%A4%B4%E5%88%B0%E5%B0%BE&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[Link 2]: https://www.baidu.com/s?wd=%E5%92%8C%E4%B8%AD&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70]: /images/20211109/b175a99d9e0d4c8eaa4cb964ef5a2592.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 1]: /images/20211109/4dbbbac4396a414684e4ec24821a0b52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190804230606723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190804230618653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTg3NjEy_size_16_color_FFFFFF_t_70 4]: /images/20211109/cbd9e69334164c7da1cdd77ce0230e91.png