C语言非递归实现最大子序和函数问题及列表调试咨询

Hey there! Let's work through your code issues step by step, then cover how to debug list (array) code in C. First, let's break down the problems in your current implementation, fix them, and finally go over practical debugging strategies.

Issues in Your Current Code #

Let's unpack each function's problems:

1. sum_lst Function #

This function is mostly correct—it calculates the sum from index debut to fin-1 (since your loop uses i < fin). The real issues come from how you call it in max_sum.

2. max_sum Function #

There are several critical bugs here:

• Static variable initialization: static int sum; defaults to 0. If your array has all negative numbers (e.g., [-5, -3, -1]), your function will return 0 instead of the largest negative number (-1), which is incorrect.
• Inner loop doesn't reset: You initialize j=0 once before the loops. After the first outer iteration, j stays at n, so all subsequent inner loops won't run—you'll never check shorter subarrays.
• Reversed parameters in sum_lst call: You wrote sum = sum_lst(lst,i,j); but should pass j as the start and i as the end (since sum_lst expects debut first, then fin). When i < j, this call returns 0, breaking your calculation.
• Inefficient subarray traversal: Your loop structure doesn't properly cover all possible subarrays. You need to check every possible start and end index pair.

Fixed Implementation (Brute Force Approach) #

First, let's fix your brute force approach (which checks all possible subarrays)—it's straightforward for beginners to follow:

#include <stdio.h>
#include <limits.h> // For INT_MIN, to handle all-negative arrays

// Calculate sum from start (inclusive) to end (inclusive)
int sum_lst(int lst[], int start, int end) {
    int sum = 0;
    for (int i = start; i <= end; i++) {
        sum += lst[i];
    }
    return sum;
}

int max_sum(int lst[], int n) {
    // Initialize max_sum to the smallest possible integer to handle all-negative arrays
    int max_sum = INT_MIN;
    
    // Iterate all possible start indices
    for (int start = 0; start < n; start++) {
        // Iterate all possible end indices (from start to end of array)
        for (int end = start; end < n; end++) {
            int current_sum = sum_lst(lst, start, end);
            // Update max_sum if current subarray sum is larger
            if (current_sum > max_sum) {
                max_sum = current_sum;
            }
        }
    }
    return max_sum;
}

// Test the function
int main() {
    int test_lst[] = {-1,4,-10,9,14,-4};
    int n = sizeof(test_lst)/sizeof(test_lst[0]);
    printf("Max subarray sum: %d\n", max_sum(test_lst, n)); // Should output 23
    return 0;
}

Even Better: Kadane's Algorithm (O(n) Time) #

If you want a more efficient solution (runs in linear time instead of O(n²)), Kadane's Algorithm is perfect for this problem—and it's non-recursive:

#include <stdio.h>
#include <limits.h>

int max_sum(int lst[], int n) {
    int current_max = lst[0];
    int global_max = lst[0];
    
    for (int i = 1; i < n; i++) {
        // Choose between starting a new subarray at lst[i] or extending the current one
        current_max = (lst[i] > current_max + lst[i]) ? lst[i] : current_max + lst[i];
        // Update global max if current subarray is larger
        if (current_max > global_max) {
            global_max = current_max;
        }
    }
    return global_max;
}

int main() {
    int test_lst[] = {-1,4,-10,9,14,-4};
    int n = sizeof(test_lst)/sizeof(test_lst[0]);
    printf("Max subarray sum: %d\n", max_sum(test_lst, n)); // Outputs 23
    return 0;
}

Debugging Array/List Code in C #

Here are simple, beginner-friendly debugging techniques:

• Print intermediate values: Add printf statements to track variables. For example, in your original max_sum, print i, j, sum_lst(lst,j,i), and sum to see where calculations go wrong:

  for (i;i>0;i--){
      printf("Outer loop: i = %d\n", i);
      j=0; // Reset j here!
      for (j;j<n;j++){
          int current_sum = sum_lst(lst,j,i);
          printf("Inner loop: j = %d, current_sum = %d, current sum = %d\n", j, current_sum, sum);
          if (current_sum > sum){
              sum = current_sum;
              printf("Updated sum to %d\n", sum);
          }
      }
  }
  

• Use a debugger (GDB): If you're using a terminal-based environment, GDB lets you set breakpoints, step through code line by line, and inspect variable values:
  1. Compile your code with debugging symbols: gcc -g your_code.c -o your_program
  2. Run GDB: gdb ./your_program
  3. Set a breakpoint at max_sum: break max_sum
  4. Run the program: run
  5. Step through each line: next (or step to enter functions)
  6. Print a variable: print sum or print lst[j]
• Test with small, simple arrays: Start with tiny arrays like [1, -2, 3] or [-5, -3] to verify your code works before moving to larger examples.

内容的提问来源于stack exchange，提问作者Doron Slomovits