黑马程序员技术交流社区

标题: 看起来很简单但是很有难度的题目 [打印本页]
作者: Alan_Kwan    时间: 2014-6-22 22:49
标题: 看起来很简单但是很有难度的题目
本帖最后由 Alan_Kwan 于 2014-6-22 22:57 编辑
  1. int [] arr = {4, -3, 5, -2, -1, 2, 6, -2};
复制代码

求它最大子序列的和，即它的子序列中和为最大的那个序列的和。
作者: 木华    时间: 2014-6-22 23:04
是不是大于零的数相加就是它的最大子序列。这样的话就很简单了。
作者: Alan_Kwan    时间: 2014-6-22 23:22
木华 发表于 2014-6-22 23:04
是不是大于零的数相加就是它的最大子序列。这样的话就很简单了。

序列是有序的队列。子序列就是指比如{4,-3,5}，而{4,5}不是。
作者: GoodBoy123    时间: 2014-6-22 23:25
完全看不懂是什么意思
作者: 陈云阳    时间: 2014-6-23 01:11
class A
{
        public static void main(String[] args)
        {
       
                int [] arr = {4, -3, 5, -2, -1, 2, 6, -2};;
                System.out.println(max_sub(arr,arr.length));
        }
        public static int max_sub(int a[],int size)
        {
                 int i,j,v,max=a[0];
                 for(i=0;i<size;i++)
                 {
                          v=0;
                          for(j=i;j<size;j++)
                          {
                                   v=v+a[j];
                                   if(v>max)
                                                max=v;
                          }
                 }
                 return max;
        }
}
穷举所有子序列   最大子序列和是11
作者: idency    时间: 2014-6-23 01:29
  1. public class Demo {

  3.         public static void main(String[] args) {
  4.                 int[] arr = { 4, -3, 5, -2, -1, 2, 6, -2 };
  5.                
  6.                 //定义一个变量接受最后的最大值
  7.                 int big = arr[0];
  8.                 //定义为数组中任意一个元素,如果定义0,在数组都为负数情况下会计算错误
  9.                
  10.                 //外围for循环取得某一子序列的开始位置,内层for循环取得任意子序列的结尾位置
  11.                 for (int i = 0; i < arr.length; i++) {
  12.                         for (int j = i; j < arr.length; j++) {
  13.                                 if (sum(arr, i, j) > big) {//如果某个子序列和大于big,将该值赋给big
  14.                                         big = sum(arr, i, j);
  15.                                 }
  16.                         }
  17.                 }

  19.                 System.out.println(big);//打印输出最后的big值
  20.         }

  22.        
  23.         //定义一个函数,计算出给出数组中从i角标开始到角标结束之间元素的和
  24.         public static int sum(int[] arr, int i, int j) {
  25.                 int sum = 0;
  26.                 for (int k = i; k <= j; k++) {
  27.                         sum += arr[k];
  28.                 }
  29.                 return sum;//返回计算的结果
  30.         }
  31. }
复制代码




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