隨筆-126  評論-247  文章-5  trackbacks-0

            
          給出一個無序數組, 找出連續的任意多個元素, 使得其和加起來是最大的, 要求時間復雜度為 O(N)

              
          //In Java
          public static int maxSubSum(int[] array){
              
          int sum = 0, max = array[0];
              
          for(int i = 0; i < array.length; i++){
                  sum 
          += array[i];
                  
          if(sum > max)
                      max 
          = sum;
                  
          if(sum < 0)  //如果 sum < 0, 將 sum 重新置 0
                      sum = 0;
              }
              
          return max;
          }
              

           

             
          //In C++
          #include <stdio.h>
          #include 
          <string.h>
          #include 
          <stdlib.h>
          #define length(array) sizeof(array) / sizeof(array[0])

          int maxSubSum(int *array, int len){
              
          int sum = 0, max = array[0];
              
          for(int i = 0; i < len; i++){
                  sum 
          += array[i];
                  
          if(sum > max)
                      max 
          = sum;
                  
          if(sum < 0)
                      sum 
          = 0;
              }
              
          return max;
          }
             


           



            
          posted on 2013-02-07 09:22 fancydeepin 閱讀(2493) 評論(3)  編輯  收藏

          評論:
          # re: 最大連續子串的和[未登錄] 2013-02-19 13:43 |
          有問題
          如 8 -1 8?  回復  更多評論
            
          # re: 最大連續子串的和[未登錄] 2013-02-19 13:44 |
          @幻
          不好意思,看錯了,激動了  回復  更多評論
            
          # re: 最大連續子串的和 2013-04-10 09:35 | dohkoos
          if (sum < 0)應該是if (sum < max)
            回復  更多評論
            

          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 陈巴尔虎旗| 信阳市| 平泉县| 望谟县| 黄龙县| 于都县| 桃园市| 云梦县| 盐津县| 辽阳县| 察隅县| 卢龙县| 龙游县| 原阳县| 绥阳县| 邯郸县| 陈巴尔虎旗| 栖霞市| 阿拉善右旗| 万州区| 枞阳县| 安吉县| 葫芦岛市| 泰和县| 睢宁县| 中宁县| 嘉黎县| 河南省| 柘荣县| 吉木乃县| 自贡市| 怀仁县| 宝清县| 平武县| 焉耆| 穆棱市| 桂林市| 基隆市| 阜宁县| 威海市| 淳化县|