Tìm dãy số có tổng lớn nhất của các phần tử trong một mảng

Question

Gần đây tôi đã phỏng vấn với một công ty và họ yêu cầu tôi viết một thuật toán tìm ra chuỗi có tổng các phần tử lớn nhất trong một mảng. Các phần tử trong mảng có thể là số âm. Có một giải pháp O (n) cho nó? Bất kỳ giải pháp tốt được đánh giá rất nhiều.

Answer 1

Nếu bạn muốn số tiền lớn nhất của số thứ tự sau đó một cái gì đó như thế này có thể làm việc:

$cur = $max = 0; 
foreach ($seq as $n) 
{ 
    $cur += $n; 
    if ($cur < 0) $cur = 0; 
    if ($cur > $max) $max = $cur; 
} 

đó chỉ là ra khỏi đỉnh đầu của tôi, nhưng có vẻ đúng. (Bỏ qua nó giả định 0 là câu trả lời cho tập hợp rỗng và tất cả các tiêu cực.)

Edit:

Nếu bạn cũng muốn vị trí trình tự:

$cur = $max = 0; 
$cur_i = $max_i = 0; 
$max_j = 1; 

foreach ($seq as $i => $n) 
{ 
    $cur += $n; 
    if ($cur > $max) 
    { 
    $max = $cur; 
    if ($cur_i != $max_i) 
    { 
     $max_i = $cur_i; 
     $max_j = $max_i + 1; 
    } 
    else 
    { 
     $max_j = $i + 1; 
    } 
    } 

    if ($cur < 0) 
    { 
    $cur = 0; 
    $cur_i = $i + 1; 
    } 
} 

var_dump(array_slice($seq, $max_i, $max_j - $max_i), $max); 

Có thể có một cách ngắn gọn hơn để làm đi. Một lần nữa, nó có cùng một giả định (ít nhất một số nguyên dương). Ngoài ra, nó chỉ tìm thấy chuỗi đầu tiên lớn nhất.

Chỉnh sửa: đã thay đổi thành sử dụng max_j (độc quyền) thay vì max_len.

Answer 2

Tôi giả sử bạn có nghĩa là dài nhất tăng sau.

Không có giải pháp O(n) cho điều đó.

Một giải pháp rất ngây thơ sẽ là tạo một mảng trùng lặp, sắp xếp nó trong O(NlogN) và sau đó tìm thấy các LCS của mảng được sắp xếp và mảng gốc mất O(N^2).

Ngoài ra còn có giải pháp dựa trên DP trực tiếp tương tự như LCS cũng mất O(N^2), bạn có thể xem here.

Nhưng nếu bạn có ý nghĩa là chuỗi tăng dài nhất (liên tiếp). Điều này có thể được thực hiện trong O(N).

Answer 3

Nếu bạn có ý nghĩa là tăng dần dài nhất, hãy xem codaddict câu trả lời của.

Nếu mặt khác bạn có nghĩa là việc tìm kiếm các mảng phụ với tổng tối đa (làm cho tinh thần duy nhất có giá trị âm), sau đó có một thanh lịch, phong cách lập trình năng động Giải pháp thời gian tuyến tính:

http://en.wikipedia.org/wiki/Maximum_subarray_problem

Answer 4

C chức năng trông như thế này:

int largest(int arr[], int length) 
{ 
    int sum= arr[0]; 
    int tempsum=0; 
    for(int i=0;i<length;i++){ 
    tempsum+=arr[i]; 
    if(tempsum>sum) 
     sum=tempsum; 
    if(tempsum<0) 
     tempsum=0; 
    } 
    return sum; 
} 

Answer 5

Hãy thử đoạn mã sau:

#include <stdio.h> 

int main(void) { 
    int arr[] = {-11,-2,3,-1,2,-9,-4,-5,-2, -3}; 
    int cur = arr[0] >= 0? arr[0] : 0, max = arr[0]; 
    int start = 0, end = 0; 
    int i,j = cur == 0 ? 1 : 0; 
    printf("Cur\tMax\tStart\tEnd\n"); 
    printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    for (i = 1; i < 10; i++) { 
     cur += arr[i]; 
     if (cur > max) { 
      max = cur; 
      end = i; 
      if (j > start) start = j; 
     }  
     if (cur < 0) { 
      cur = 0; 
      j = i+1; 
     } 
     printf("%d\t%d\t%d\t%d\n",cur,max,start,end); 
    } 
    getchar(); 
} 

Answer 6

void longsub(int a[], int len) { 

     int localsum = INT_MIN; 
     int globalsum = INT_MIN; 
     int startindex = 0,i=0; 
     int stopindex = 0; 
     int localstart = 0; 

     for (i=0; i < len; i++) { 
       if (localsum + a[i] < a[i]) { 
         localsum = a[i]; 
         localstart = i; 
       } 
       else { 
         localsum += a[i]; 
       } 

       if (localsum > globalsum) { 
         startindex = localstart; 
         globalsum = localsum; 
         stopindex = i; 
       } 

     } 

     printf ("The begin and end indices are %d -> %d (%d).\n",startindex, stopindex, globalsum); 

} 

Answer 7

Vấn đề này có thể được giải quyết hai cách khác nhau.

Cách tiếp cận đầu tiên có hai biến được gọi là sum và MaxSum.

1. Chúng tôi sẽ tiếp tục bổ sung thêm giá trị cho tổng và sẽ so sánh với MaxSum, nếu giá trị với tổng số tiền lớn hơn MaxSum - sẽ gán giá trị tổng cho MaxSum

2. Nếu trong xử lý giá trị cho tổng đi dưới 0, chúng tôi sẽ đặt lại tổng và sẽ bắt đầu thêm số mới từ chỉ mục tiếp theo trên các phường. Mẫu mã cho các giải pháp trên được cung cấp như sau:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = 0; 
       int MaxSum = 0; 
   
       for (int i = 0; i < array.Length; i++) 
       { 
        sum += array[i]; 
   
        if (sum > MaxSum) 
        { 
         MaxSum = sum; 
        } 
        else if (sum < 0) 
        { 
         sum = 0; 
        } 
       } 
       Console.WriteLine("Maximum sum is: " + MaxSum); 
   } 
   

Cách tiếp cận thứ hai để giải quyết vấn đề này là chúng ta sẽ đi qua từng phần tử trong một mảng. Chúng ta sẽ có cùng 2 biến sum và MaxSum.

1. Trước tiên, chúng tôi sẽ so sánh việc cộng tổng với phần tử mảng tiếp theo và tổng số tiền. Ai bao giờ lớn hơn - giá trị đó sẽ được lưu trữ trong biến tổng.

2. Tiếp theo, chúng tôi sẽ so sánh các giá trị của tổng và MaxSum và bất kỳ ai có giá trị lớn hơn - chúng tôi sẽ lưu giá trị đó trong biến MaxSum. Mẫu mã là như đã đề cập dưới đây:

   private static void FindMaxSum(int[] array) 
   { 
       int sum = array[0], Maxsum = array[0]; 
   
       for (int i = 1; i < array.Length; i++) 
       { 
        sum = Max(sum + array[i], array[i]); 
        Maxsum = Max(sum, Maxsum);    
       } 
   
       Console.WriteLine("Maximum sum is: " + Maxsum); 
   } 
   
   private static int Max(int a, int b) 
   { 
       return a > b ? a : b; 
   } 
   

Answer 8

Nếu bạn đang yêu cầu một dãy liền kề mà tổng là tối đa, tôi đã tìm thấy 4 algos cho đến nay là gì: -

1. Brute-lực: Tìm tất cả các khoản tiền có thể bằng cách sử dụng vòng lặp lồng nhau và tiếp tục cập nhật maxSum nếu bạn tìm thấy một tổng lớn hơn giá trị thiết lập trước đó của maxSum. Sự phức tạp thời gian là O (n^2)

2. Giải pháp lập trình động: Đây là một giải pháp khá thanh lịch mà tôi tìm thấy trên StackOverflow bản thân - https://stackoverflow.com/a/8649869/2461567v - Thời gian phức tạp: O (n), Space phức tạp: O (n)

3. DP mà không cần bộ nhớ - Kadane Algorithm - https://en.wikipedia.org/wiki/Maximum_subarray_problem - Thời gian phức tạp: O (n), Space phức tạp: O (1)

4. Divide and Conquer Solution - http://eecs.wsu.edu/~nroy/courses/CptS223/notes/MaxSubsequenceSum.pdf Thời gian phức tạp: O (nlgn)