具有最大和的子阵列的大小-yiteyi-C++库

给出一个数组，求和最大的子数组的长度。

null

例如：

Input :  a[] = {1, -2, 1, 1, -2, 1}Output : Length of the subarray is 2Explanation: Subarray with consecutive elements and maximum sum will be {1, 1}. So length is 2Input : ar[] = { -2, -3, 4, -1, -2, 1, 5, -3 }Output : Length of the subarray is 5Explanation: Subarray with consecutive elements and maximum sum will be {4, -1, -2, 1, 5}.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个问题主要是最大和邻接子阵问题 . 这样做的目的是每当结束于此的和小于0时更新起始索引。

C++

                         // C++ program to print length of the largest                       
                         // contiguous array sum                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     maxSubArraySum(                                     int                                     a[],                                     int                                     size)                       
                         {                       
                                                 int                                     max_so_far = INT_MIN, max_ending_here = 0,                       
                                                 start =0, end = 0, s=0;                       
           
                                                 for                                     (                                     int                                     i=0; i< size; i++ )                       
                                                 {                       
                                                 max_ending_here += a[i];                       
           
                                                 if                                     (max_so_far < max_ending_here)                       
                                                 {                       
                                                 max_so_far = max_ending_here;                       
                                                 start = s;                       
                                                 end = i;                       
                                                 }                       
           
                                                 if                                     (max_ending_here < 0)                       
                                                 {                       
                                                 max_ending_here = 0;                       
                                                 s = i + 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     (end - start + 1);                       
                         }                       
           
                         /*Driver program to test maxSubArraySum*/                       
                         int                                     main()                       
                         {                       
                                                 int                                     a[] = {-2, -3, 4, -1, -2, 1, 5, -3};                       
                                                 int                                     n =                                     sizeof                                     (a)/                                     sizeof                                     (a[0]);                       
                                                 cout << maxSubArraySum(a, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to print length of the largest                       
                         // contiguous array sum                       
                         class                                     GFG {                       
           
                                                 static                                     int                                     maxSubArraySum(                                     int                                     a[],                                     int                                     size)                       
                                                 {                       
                                                 int                                     max_so_far = Integer.MIN_VALUE,                       
                                                 max_ending_here =                                     0                                     ,start =                                     0                                     ,                       
                                                 end =                                     0                                     , s =                                     0                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < size; i++)                       
                                                 {                       
                                                 max_ending_here += a[i];                       
           
                                                 if                                     (max_so_far < max_ending_here)                       
                                                 {                       
                                                 max_so_far = max_ending_here;                       
                                                 start = s;                       
                                                 end = i;                       
                                                 }                       
           
                                                 if                                     (max_ending_here <                                     0                                     )                       
                                                 {                       
                                                 max_ending_here =                                     0                                     ;                       
                                                 s = i +                                     1                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     (end - start +                                     1                                     );                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     a[] = { -                                     2                                     , -                                     3                                     ,                                     4                                     , -                                     1                                     , -                                     2                                     ,                                     1                                     ,                                     5                                     , -                                     3                                     };                       
                                                 int                                     n = a.length;                       
                                                 System.out.println(maxSubArraySum(a, n));                       
                                                 }                       
                         }                       

Python3

                         # Python3 program to print largest contiguous array sum                       
           
                         from                                     sys                                     import                                     maxsize                       
           
                         # Function to find the maximum contiguous subarray                       
                         # and print its starting and end index                       
                         def                                     maxSubArraySum(a,size):                       
           
                                                 max_so_far                                     =                                     -                                     maxsize                                     -                                     1                       
                                                 max_ending_here                                     =                                     0                       
                                                 start                                     =                                     0                       
                                                 end                                     =                                     0                       
                                                 s                                     =                                     0                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     ,size):                       
           
                                                 max_ending_here                                     +                                     =                                     a[i]                       
           
                                                 if                                     max_so_far < max_ending_here:                       
                                                 max_so_far                                     =                                     max_ending_here                       
                                                 start                                     =                                     s                       
                                                 end                                     =                                     i                       
           
                                                 if                                     max_ending_here <                                     0                                     :                       
                                                 max_ending_here                                     =                                     0                       
                                                 s                                     =                                     i                                     +                                     1                       
           
                                                 return                                     (end                                     -                                     start                                     +                                     1                                     )                       
           
                         # Driver program to test maxSubArraySum                       
                         a                                     =                                     [                                     -                                     2                                     ,                                     -                                     3                                     ,                                     4                                     ,                                     -                                     1                                     ,                                     -                                     2                                     ,                                     1                                     ,                                     5                                     ,                                     -                                     3                                     ]                       
                         print                                     (maxSubArraySum(a,                                     len                                     (a)))                       

C#

                         // C# program to print length of the                       
                         // largest contiguous array sum                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Function to find maximum subarray sum                       
                                                 static                                     int                                     maxSubArraySum(                                     int                                     []a,                                     int                                     size)                       
                                                 {                       
                                                 int                                     max_so_far =                                     int                                     .MinValue,                       
                                                 max_ending_here = 0,start = 0,                       
                                                 end = 0, s = 0;                       
           
                                                 for                                     (                                     int                                     i = 0; i < size; i++)                       
                                                 {                       
                                                 max_ending_here += a[i];                       
           
                                                 if                                     (max_so_far < max_ending_here)                       
                                                 {                       
                                                 max_so_far = max_ending_here;                       
                                                 start = s;                       
                                                 end = i;                       
                                                 }                       
           
                                                 if                                     (max_ending_here < 0)                       
                                                 {                       
                                                 max_ending_here = 0;                       
                                                 s = i + 1;                       
                                                 }                       
                                                 }                       
                                                 return                                     (end - start + 1);                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []a = {-2, -3, 4, -1, -2, 1, 5, -3};                       
                                                 int                                     n = a.Length;                       
                                                 Console.Write(maxSubArraySum(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by parashar...                       

PHP

                         <?php                       
                         // PHP program for Bresenham’s                       
                         // Line Generation Assumptions :                       
           
                         // 1) Line is drawn from                       
                         // left to right.                       
                         // 2) x1 < x2 and y1 < y2                       
                         // 3) Slope of the line is                       
                         // between 0 and 1.                       
                         // We draw a line from lower                       
                         // left to upper right.                       
           
                         // function for line generation                       
                         function                                     bresenham(                                     $x1                                     ,                                     $y1                                     ,                                     $x2                                     ,                                     $y2                                     )                       
                         {                       
                         $m_new                                     = 2 * (                                     $y2                                     -                                     $y1                                     );                       
                         $slope_error_new                                     =                                     $m_new                                     - (                                     $x2                                     -                                     $x1                                     );                       
                         for                                     (                                     $x                                     =                                     $x1                                     ,                                     $y                                     =                                     $y1                                     ;                                     $x                                     <=                                     $x2                                     ;                                     $x                                     ++)                       
                         {                       
                                                 echo                                     "("                                     ,                                     $x                                     ,                                     ","                                     ,                                     $y                                     ,                                     ")"                                     ;                       
           
                                                 // Add slope to increment                       
                                                 // angle formed                       
                                                 $slope_error_new                                     +=                                     $m_new                                     ;                       
           
                                                 // Slope error reached limit,                       
                                                 // time to increment y and                       
                                                 // update slope error.                       
                                                 if                                     (                                     $slope_error_new                                     >= 0)                       
                                                 {                       
                                                 $y                                     ++;                       
                                                 $slope_error_new                                     -= 2 * (                                     $x2                                     -                                     $x1                                     );                       
                                                 }                       
                         }                       
                         }                       
           
                         // Driver Code                       
                         $x1                                     = 3;                                     $y1                                     = 2;                                     $x2                                     = 15;                                     $y2                                     = 5;                       
                         bresenham(                                     $x1                                     ,                                     $y1                                     ,                                     $x2                                     ,                                     $y2                                     );                       
           
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to print length                       
                         // of the largest contiguous array sum                       
                         function                                     maxSubArraySum(a, size)                       
                         {                       
                                                 let max_so_far = Number.MIN_VALUE,                       
                                                 max_ending_here = 0,start = 0,                       
                                                 end = 0, s = 0;                       
           
                                                 for                                     (let i = 0; i < size; i++)                       
                                                 {                       
                                                 max_ending_here += a[i];                       
           
                                                 if                                     (max_so_far < max_ending_here)                       
                                                 {                       
                                                 max_so_far = max_ending_here;                       
                                                 start = s;                       
                                                 end = i;                       
                                                 }                       
           
                                                 if                                     (max_ending_here < 0)                       
                                                 {                       
                                                 max_ending_here = 0;                       
                                                 s = i + 1;                       
                                                 }                       
                                                 }                       
                                                 return                                     (end - start + 1);                       
                         }                       
           
                         // Driver code                       
                         let a = [ -2, -3, 4, -1, -2, 1, 5, -3 ];                       
                         let n = a.length;                       
           
                         document.write(maxSubArraySum(a, n));                       
           
                         // This code is contributed by splevel62                       
           
                         </script>                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章