04/03: Interview Question :Get Maximum Sum of subarray

给定一个长度为n的一维数组a，请找出此数组的一个子数组,使得此子数组的和sum＝a[i]+a[i+1]+……+a[j]最大，其中i>=0,i<n,j>=i,j<n，例如
   31 -41 59 26 -53  58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。

 

 

1. －直接穷举法:(O(n3)

public int GetSubArrayMaximum()
      {
          int maxresult=0;
          int[] a = new int[] { -8, 6, 3, -2, 4, -10 };
          for (int i = 0; i < a.Length; i++)
          {
              for(int j=i;j<a.Length;j++)
              {
                  int sum=0;
                  for(int k=i;k<=j;k++)
                  {
                      sum+=a[k];
                      if(sum>maxresult)
                      {
                          maxresult=sum;
                      }

                  }

              }
          }

      return maxresult;

      }

 

}

2.(O(n)

当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和

int[] input = new int[] { 3, 73, -95, 42, 43, 29, -30 ,1};
               //, -87, 74, -53, 22, 74, -91, -1, -27, -8, -14, 26, -67, -74 };
           //fst is first element of return array
           //snd  is end element of return array
           //maxsum is the sum of return array
           int fst = -1, snd = -1, tFst = 0, tSnd = 0, maxSum = 0, currSum = 0;
           for (; tSnd < input.Length; ++tSnd)
           {
               currSum += input[tSnd];
               if (currSum > maxSum)
               {
                   maxSum = currSum;
                   fst = tFst;
                   snd = tSnd;
               }
               if (currSum < 0)
               {
                   currSum = 0;
                   tFst = tSnd + 1;
               }
           }

 

  // if all data are negative, find the greatest element in the array

if(maxSum<0)

{

// find the greatest element of array

…

}