给一个数组,元素都是整数(有正数也有负数),寻找连续的元素相加之和为最大的序列。
如:1、-2、3、5、-4、6连续序列3、5、-4、6的和最大。
如元素全为负数,则最大的和为0,即一个也没有选。
@Test public void test5(){ int[] nums = new int[]{1,-2,3,5,-4,6}; int maxNum = 0; int sum = 0; for (int i = 0; i < nums.length; i++) { for(int j=i;j<nums.length;j++){ for (int k = i; k <= j; k++) { sum += nums[k]; } if(sum>maxNum){ maxNum = sum; } sum = 0; } } System.out.println(maxNum); }
@Test public void testMaxSum2(){ int[] nums = new int[]{1,-2,3,5,-4,6}; int maxNum = nums[0]; int sum = 0; for (int i = 0; i < nums.length; i++) { if(sum>=0){ sum += nums[i]; }else{ sum = nums[i]; } if(sum > maxNum){ maxNum = sum; } } System.out.println(maxNum); }
/* array[] 输入数组 n 数组元素个数 返回最大序列和 */ int find_max_sum(int array[],int n) 1.int find_max_sum(int array[],int n) 2.{ 3. int i,max,sum; 4. sum=max=array[0]; 5. for(i=1;i<n;++i) 6. { 7. if(sum<0) 8. sum=array[i]; 9. else 10. sum+=array[i]; 11. if(sum>max) 12. max=sum; 13. } 14. if(max<0) 15. max=0; 16. return max; 17.}